Competitive-Programming/Segment_tree.cpp at master · wargraver/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int diff;
vector<int> vect;
int buildtree(int i,int st,int en,vector<int> nums){
        if(st==en) return vect[i] = nums[st];
        else if(st>en) return 0;
        else{
            int mid = (st+en)/2;
            vect[i] = buildtree(2*i+1,st,mid,nums) +  buildtree(2*i+2,mid+1,en,nums);
            return vect[i];
        }
    }
int get_sum(int i,int st,int en,int left,int right){
    if(st>en) return 0;
    else if(st>right || en<left) return 0;
    else{
        if(st>=left && en<=right) return vect[i];
        else{
            int mid = (st+en)/2;
            return get_sum(2*i+1,st,mid,left,right) + get_sum(2*i+2,mid+1,en,left,right);
        }
    }
}
void get_updated(int i,int st,int en,int index,int val){
    if(st>en) return;
    else if(st==en && st==index){
        diff = val-vect[i];
        vect[i] = val;
        return;
    }
    else{
        if(st>index || en<index) return;
        else{
            int mid = (st+en)/2;
            get_updated(2*i+1,st,mid,index,val);
            get_updated(2*i+2,mid+1,en,index,val);
            vect[i] = vect[i]+diff;
        }
    }
}
class NumArray {
public:
    int cap;
    NumArray(vector<int>& nums) {
        int m = nums.size();
        vect.clear();
        for(int i=0;i<=4*m;i++) vect.push_back(0);
        int st=0,en=m-1;
        this->cap=en;diff=0;
        buildtree(0,st,en,nums);
    }
    void update(int index, int val) {
         int st=0,en=this->cap;
        get_updated(0,st,en,index,val);
    }

    int sumRange(int left, int right) {
        int st=0,en=this->cap;
        return get_sum(0,st,en,left,right);
    }
};