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?