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?


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.