I have gone through few tutorials of Range update - Range queries of Binary indexed tree. I'm unable to understand any of them. I don't understand the need of building another tree.
Could someone explain it to me in plain English with an example?
Trying to explain in more intuitive way (the way I understood). I'll divide it in four steps:
Assume the update is between A and B with V and the query is a prefix query for any index <=X
The first is a simple range update/point query tree. When you update A to B with V, in practice you add V to position A, so any prefix query X>=A is affected by it. Then you remove V from B+1, so any query X >= B+1 doesn't see the V added to A. No surprises here.
The T1.sum(X) is a point query to this first tree at X. We optimistically assume then that every element before X is equal to the value at X. That's why we do T1.sum(X)*X. Obviously this isn't quite right, that's why we:
When updating the range, we also update a second tree to tell how much we have to fix the first T1.sum(X)*X query. This update consists in removing (A-1)*V from any query X>=A. Then we add back B*V for X>=B. We do the latter because queries to the first tree won't return V for X>=B+1 (because of the T1.add(B+1, -V)), so we need to somehow tell that there is a rectangle of area (B-A+1)*V for any query X>=B+1. We already removed (A-1)*V from A, we only need to add back B*V to B+1.
update(A, B, V):
T1.add(A, V) # add V to any X>=A
T1.add(B+1, -V) # cancel previously added V from any X>=B+1
T2.add(A, (A-1)*V) # add a fix for (A-1)s V that didn't exist before A
T2.add(B+1, -B*V) # remove the fix, and add more (B-A+1)*V to any query
# X>=B+1. This is really -(A-1)*V -(B-A+1)*V, but it
# simplifies to -B*V
sum(X):
return T1.sum(X)*X - T2.sum(X)