Fenwick tree with a modification on the segment

This data structure can be found in this post and its modification to find the maximum in it . But I never met the implementation with the change of elements in the segment, so I decided to share what I managed to get on my own.

1. Statement of the problem

There is an array. You must be able to fulfill two types of requests:

1. Modification - add d to each element of the segment [l, r]
2. Amount - calculate the sum of the elements of the segment [l, r]

2. Description of the solution

It is easy to see that both types of queries can be “facilitated” to the segment [0, r] by breaking the segment [l, r] into two prefixes. As for the segment tree, we will create the second array, in which we will store as much as necessary to add to all the numbers of this segment.

Create a Fenwick class with prototypes of future methods.

class Fenwick{ int *m, *mt, N; public: Fenwick(int n); Fenwick(int a[], int n); void add_range(int r, int d); void add_range(int l, int r, int d); int sum(int r); int sum(int l, int r); }; 

')
In the first constructor, it suffices to allocate memory and zero the elements of the array. And in the second we will go through the array a and convert the values ​​in the tree.

 Fenwick::Fenwick(int n){ N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); } Fenwick::Fenwick(int a[], int n){ N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); for(int i=0;i<N;++i){ m[i] += a[i]; if((i|(i+1))<N) m[i|(i+1)] += m[i]; } } 

Consider now the change operation. Suppose the query came "add 1 to the elements of the segment [0, 9]." This segment is completely covered by non-intersecting segments [0, 7] and [8, 9], therefore in 7 and 9 elements of the mt array we add 1. But there are segments containing [0, 9] (or part of it) as a subsegment. They are all located on the right. For them, it is necessary to change the value in the array m to as many as the elements of the segment [0, 9] they contain. That is, in m [11] add 2, and to m [15] - 10.



It can be seen from the figure that the movements occur according to the same laws as in the trivial implementation of the Fenwick tree, so we will immediately move on to the code.

 void Fenwick::add_range(int r, int d){ if(r<0) return ; for(int i=r;i>=0;i=(i&(i+1))-1) mt[i] += d; for(int i=r|(r+1);i<N;i|=i+1) m[i] += d*(r-(i&(i+1))+1); } void Fenwick::add_range(int l, int r, int d){ add_range(r, d); add_range(l-1, -d); } 

For the sum on the prefix, the same picture is suitable with the only explanation that for green elements you need to add both m and mt, and for blue ones only mt (that is, take into account large covering segments).

 int Fenwick::sum(int r){ if(r<0) return 0; int res = 0; for(int i=r;i>=0;i=(i&(i+1))-1) res += m[i] + mt[i]*(i-(i&(i+1))+1); for(int i=r|(r+1);i<N;i|=i+1) res += mt[i]*(r-(i&(i+1))+1); return res; } int Fenwick::sum(int l, int r){ return sum(r) - sum(l-1); } 

3. Results

We managed to get a data structure with initialization for O (N), modification and sum on a segment for O (logN). On a random test with 10,000,000 items and 10,000,000 requests received the following figures:

Data structure	Initialization	Modification	Amount
Fenwick	0.13 s	9.12 s	8.90 s
RSQ ( implementation with e-maxx )	0.25 s	17.13 s	13.53 seconds