I have read some tutorials on Binary Indexed Tree, but i'm not able to understand how to implement it when query and update both operations are in some range.
To implement range update and range query, you need to know about range update and point query ( update [a,b] with v; query(x) gives the value at A[x]).
We'll use two BIT's to implement range update and range query.
Let's say the array is initialized to 0. If we update [a,b] with v,
For some x, sum(0,x) = 0 if 0 < x < a
= v*(x - (a-1)) if a <= x <= b
= v * (b - (a-1)) if b < x
where v is the value at A[x] (calculated via BIT1)
From the above formula, we'll find T, when subtracted from v*x (v is calculated from BIT1) we get the result.
if 0 < x < a : sum(0,x) = 0, T = 0
a <= x <= b: sum(0,x) = v*x - v*(a-1) , T = v*(a-1)
b < x : sum(0,x) = v*(b-a+1) , T = -v*(b-(a-1)) (since A[x] = 0 when x > b)
We store T in second BIT (BIT2)
Now, to implement update [a,b] with v:
update(a,v) ; update(b+1,-v) in BIT1 and
update(a,v*(a-1)); update(b+1,-v*b) in BIT2
sum[0,x]:
QueryBIT1(x)*x - QueryBIT2(x); // call query() on corresponding BIT
where, update(index,value) and Query(index) are implementations that are used for point update and range query.
For, further details:
http://zobayer.blogspot.in/2013/11/various-usage-of-bit.html https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/