binary index tree c 2b 2b

1class bit{
2public:
3    int n;
4    vector<int> tree;
5
6    bit(){};
7    bit(int _n){
8        n=_n;
9        tree.resize(n+1);
10    };
11
12    void update(int idx,int val){
13        while(idx<=n){
14            tree[idx]+=val;
15            idx+=idx&(-idx);
16        }
17    };
18
19    int read(int idx){
20        int res=0;
21        while(idx>0){
22            res+=tree[idx];
23            idx-=idx&(-idx);
24        }
25        return res;
26    };
27
28    int sum(int L,int R){
29        return read(R)-read(L-1);
30    };
31};