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

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?

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)