Need clear explanation to Range updates and Range queries in Binary Indexed trees?

Question

I have gone through few tutorials about how to perform range updates and range queries using Binary indexed tree. I have even gone through Range update + range query with binary indexed trees . I'm unable to understand the need of second tree. In the tutorial http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree :

It says as:

Consider a range update query – Add $\mathrm{val}$ to $[i,\dots,j]$. We will design a sum function, where we consider a summation function for all possible $x$ as following:

0ドル$ for 0ドル \leq x < i$
$\mathrm{val} * (x - (i - 1))$ for $i \leq x \leq j$
$\mathrm{val} * (j - (i - 1))$ for $j < x < n$

I just want to know the following things:

If $i\leq x\leq j$, why is the sum $\mathrm{val}*(x-(i-1))$ ?

I'm not able to appreciate the entire algorithm.

Could someone explain me using examples?

Answer 1

Consider an array $A[0, \cdots, n-1]$ and its cumulative sum array $A'$. Suppose we want to make a range update of $v$ to $A[i, \cdots, j]$. Then $A'$ is changed in the following way:

• For 0ドル \le x < i$: $A'[x]$ does not change;
• For $i \le x \le j$: $A'[x]$ is added by $v \ast \left( x-(i-1) \right)$;
• For $j < x < n$: $A'[x]$ is added by $v \ast \left( j-(i-1) \right)$.

---

For your question, why is $v \ast \left( x-(i-1) \right)$?

First, the specification of range update of BIT Range-Update(v,i,j) means adding value $v$ to each element of $A[i, \cdots, j]$.

Secondly, $A'$ stores the cumulative sums of $A$. For $A'[x], i \le x \le j,ドル its increment consists of the cumulatively added values preceding it, which is, along with $v$ of itself, $v \ast \left( x-(i-1) \right)$. The increment of $A'[x], j < x < n$ is the same as that of $A'[j],ドル which is $v \ast \left( j-(i-1) \right)$.

---

An example from the post you mentioned is as follows (thanks @JS1; the indices starts from 1 for consistency):

Suppose you had an empty array:

0 0 0 0 0 0 0 0 0 0 (array)
0 0 0 0 0 0 0 0 0 0 (cumulative sums)

And you wanted to make a range update of +5 to [4..8]:

0 0 0 5 5 5 5 5 0 0 (array)
0 0 0 5 10 15 20 25 25 25 (desired cumulative sums)