Hello, I'd like to share a cool trick, i came across recently. No doubt some people will be familiar with this, but i believe many won't be, simply because when it comes to Lazy Propagation most people use segment trees in contest. This method, although not as flexible, is far simpler. Not to mention a lot easier to code with a lot less lines of code. Also while Fenwick Tree and Segment Tree have the same complexities, in practice Fenwick Tree is usually faster.

Before we begin, I'd like to say that you should have at least a decent understanding of binary indexed trees (BITs).

We know by now, that *BIT* can be used to support following two operations:

1) *Query*(*i*) — queries element at position *i*.

2) *Update*(*i*, *j*, *d*) — adds *d* to the elements from *i* to *j*.

Some people call this "range update, single query", what we would like to accomplish is "range Update, range Query".

1) *RangeQuery*(*i*, *j*) — returns the sum from *i* to *j*.

2) *RangeUpdate*(*i*, *j*, *d*) — adds *d* to the elements from *i* to *j*.

Just to illustrate *RangeUpdate* function suppose our array has 5 elements, all initialized to zero, and we call RangeUpdate(2, 3, 3). Our array should turn from {0, 0, 0, 0, 0} to {0, 3, 6, 6, 6}.

In order to achieve this we'd need to examine what should happen when we call the function *Update*(*i*, *j*, *d*). For some arbitrary index, denoted as *idx*, we can differentiate three cases:

Case 1) *idx* < *i*, these elements remain unchanged.

Case 2) *i* ≤ *idx* ≤ *j*, element at index *i* is increased by *d*, element at index *i* + 1 is increased by 2·*d* and so on... So element at index *idx* is increased by (*idx* - *i* + 1)·*d* = *idx*·*d* - (*i* - 1)·*d*.

Case 3) *idx* > *j*, every element here is increased by a constant amount, (*j* - *i* + 1)·*d* = 0·*idx* - ( - *j* + *i* - 1)·*d*.

Here i have intentionally written values at every index as ** idx·C1 - C2**, where

*C*1 and

*C*2 are

**constants**and

*idx*is the only independent variable. We can use two

*BITs*to keep track of

*C*1 and

*C*2 values, let's call them

*bitAdd*and

*bitSub*, and our answer is simply

*idx*·

*bitAdd*.

*Query*(

*idx*) -

*bitSub*.

*Query*(

*idx*).

Finally to put it all together here is how we are going to implement lazy propagation:

*RangeUpdate*(*i*, *j*, *d*):

Case 1) *idx* < *i*, we do nothing with *bitAdd* and *bitSub*, since elements here don't change.

Case 2) *i* ≤ *idx* ≤ *j*, we call *bitAdd*.*upate*(*i*, *j*, *d*) and we call *bitSub*.*update*(*i*, *j*, (*i* - 1) * *d*).

Case 3) *idx* > *j*, we only call *bitSub*.*update*(*j* + 1, *n*, ( - *j* + *i* - 1) * *d*).

*RangeQuery*(*i*, *j*):

We know that *Sum*[1..*idx*] = *idx*·*bitAdd*.*Query*(*idx*) - *bitSub*.*Query*(*idx*).

*RangeQuery*(*i*, *j*) = *Sum*[1..*j*] - *Sum*[1..*i* - 1]

Here is my (untested) implementation of the idea : http://ideone.com/mGlJs2

Please feel free to post any questions that you might still have, and to point out any spelling\grammar mistakes :)

Yes, this idea has been discussed previously in Petr's blog as well.

Pushkar Mishra has presented a paper regarding the same(but well presented and generalized to higher dimensions) here.

I personally prefer segment trees because they are easier to think of(at least for me) :D

I've been thinking what if the RangeUpdate(i,j,k) were to make all the values from index i to index j equal to k.

For example, if initial array was -> {1,2,4,5,2}

After RangeUpdate(1,3,8) the array would be like -> {1,8,8,8,2}

and RangeQuery(i,j) would return the summation of values from index i to index j.

i can think of an idea with lazy propagation . But, How can i do this with BIT ?

Did you find any solution for that?

Not possible with BIT.

You took 3 years to find it's not possible with BIT ?

YES i'm that dumb :P

Did you Find the solution for this using BIT or Segment trees ?

bit is only possible in n log^2 n.

n log n lazy tag in bit is impossible.

for segment tree it's a ez problem.