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 :)