Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Fenwick_Tree_Sum
- {
- vector<int> tree;
- Fenwick_Tree_Sum(const vector<int>& Arg)//Arg is our array on which we are going to work
- {
- tree.resize(Arg.size());
- for(int i = 0 ; i<tree.size(); i++)
- increase(i, Arg[i]);
- }
- // Increases value of i-th element by ''delta''.
- void increase(int i, int delta)
- {
- for (; i < (int)tree.size(); i |= i + 1)
- tree[i] += delta;
- }
- // Returns sum of elements with indexes left..right, inclusive; (zero-based);
- int getsum(int left, int right)
- {
- return sum(right) - sum(left-1); //when left equals 0 the function hopefully returns 0
- }
- int sum(int ind)
- {
- int sum = 0;
- while (ind>=0)
- {
- sum += tree[ind];
- ind &= ind + 1;
- ind--;
- }
- return sum;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement