
The classical solution is to use segment trees + lazy propagation instead; however, there is a way to do it with binary indexed trees as well.
Let's think of the sum across a range [a,b) as a sum of the following function:f(x) = 0 if x<a
f(x) = k if a<=x<b
f(x) = 0 if b<=x
Now with the sum of f(0..x) as g(x):g(x) = 0 if x<a
g(x) = k(1+xa) if a<=x<b
g(x) = k( ba) if b<=x
We'll represent g(x) as the sum of two functions:g(x) = u(x) + v(x)
u(x) = k(1+xa) if a<=x
v(x) =k(1+xa) + k(ba) if b<=x
To store cumulative sums of linear functions {y = mx + c} we need to use two separate BITs, one for "m" (coefficient of x) and one for "c". The insertion of a single function would look something like this:void insert_function(int x0,int m,int c){
fenwick_m.add(x0,+m);
fenwick_c.add(x0,+c);
}
int resolve_function(int x)
return x*fenwick_m.get(x) + fenwick_c.get(x);
}
The neat thing about this technique is that it generalises to quadratic, cubic, etc. functions which allows some pretty nifty solutions to problems that would require a huge amount of work with segment trees. One such problem is http://www.spoj.pl/problems/PYRSUM2 