Problem 43: Segment Tree Range Sum

Problem Statement: Implement a segment tree to support point updates and range sum queries. Given an initial array and a sequence of queries, update elements or answer sum queries on subarrays.

Input

The first line contains two integers n and q. The second line contains n space-separated integers. Each of the next q lines contains a query in one of the following formats: 1 pos val (update the element at position pos to val) 2 l r (query the sum of the range [l, r]) Note: 1-indexed positions.

Output

For each query of type 2, print the sum of the specified range.

Examples

Solution in C++


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

class SegmentTree {
    int n;
    vector<long long> tree;
public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4*n);
        build(arr, 0, n-1, 0);
    }
    
    void build(vector<int>& arr, int l, int r, int idx){
        if(l == r){
            tree[idx] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(arr, l, mid, 2*idx+1);
        build(arr, mid+1, r, 2*idx+2);
        tree[idx] = tree[2*idx+1] + tree[2*idx+2];
    }
    
    void update(int pos, int val, int l, int r, int idx){
        if(l == r){
            tree[idx] = val;
            return;
        }
        int mid = (l+r)/2;
        if(pos <= mid) update(pos, val, l, mid, 2*idx+1);
        else update(pos, val, mid+1, r, 2*idx+2);
        tree[idx] = tree[2*idx+1] + tree[2*idx+2];
    }
    
    long long query(int ql, int qr, int l, int r, int idx){
        if(ql > r || qr < l) return 0;
        if(ql <= l && r <= qr) return tree[idx];
        int mid = (l+r)/2;
        return query(ql, qr, l, mid, 2*idx+1) + query(ql, qr, mid+1, r, 2*idx+2);
    }
    
    void update(int pos, int val){
        update(pos, val, 0, n-1, 0);
    }
    
    long long query(int l, int r){
        return query(l, r, 0, n-1, 0);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q; cin >> n >> q;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin >> arr[i];
    SegmentTree st(arr);
    while(q--){
        int type; cin >> type;
        if(type == 1){
            int pos, val; cin >> pos >> val; 
            st.update(pos-1, val);
        } else {
            int l, r; cin >> l >> r;
            cout << st.query(l-1, r-1) << "\n";
        }
    }
    return 0;
}