Problem 44: Range Update and Point Query (Fenwick Tree)

Problem Statement: Given an array and q queries, support two types of operations using a Fenwick Tree: 1) add a value to all elements in the range [l, r], and 2) output the value at index i. Initially, the array is given.

Input

The first line contains two integers n and q. The second line contains n space-separated integers (initial array). The next q lines contain queries in one of the following formats: 1 l r val (add 'val' to each element in [l, r]) 2 i (query the value at index i) Note: 1-indexed.

Output

For each query of type 2, print the value at the specified index.

Examples


Input:
5 4
1 2 3 4 5
1 1 3 2
2 2
1 2 5 1
2 3

Output:
4
6

Solution in C++


#include <iostream>
#include <vector>
using namespace std;

struct Fenwick{
    int n;
    vector<long long> bit;
    Fenwick(int n): n(n), bit(n+1, 0) {}
    
    void update(int idx, long long delta){
        for(; idx <= n; idx += idx & -idx)
            bit[idx] += delta;
    }
    
    long long query(int idx){
        long long sum = 0;
        for(; idx > 0; idx -= idx & -idx)
            sum += bit[idx];
        return sum;
    }
    
    // Range update: add delta to [l, r]
    void range_update(int l, int r, long long delta){
        update(l, delta);
        update(r+1, -delta);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q; cin >> n >> q;
    vector<int> arr(n+1);
    for (int i=1; i<=n; i++) cin >> arr[i];
    Fenwick fenw(n);
    // build BIT using initial array differences
    for (int i=1; i<=n; i++){
        int diff = arr[i] - (i>1 ? arr[i-1] : 0);
        fenw.update(i, diff);
    }
    while(q--){
        int type; cin >> type;
        if(type == 1){
            int l, r, val; cin >> l >> r >> val;
            fenw.range_update(l, r, val);
        } else {
            int i; cin >> i;
            cout << fenw.query(i) << "\n";
        }
    }
    return 0;
}