BIT: range updates, point queries; true meaning of tree[x] for the past few days I've been studying Binary Indexed Tree (aka. Fenwick tree) data structure.

I understand the basic form of BIT (point update, range query), and I see the intuition behind it, but when it comes to range update - point query BIT I don't see the intuition behind it.

Let me be more specific:


let tree be an array where we represent our BIT
let A be an ordinary array where our array values are stored. both tree and A are initially zero


For the point update - range query, we know that tree[x], where x is some index, stores cumulative frequency for elements(values) [x - 2^r + 1, ... , x], where r is position of the last non-zero bit (looking from left to right in binary notation of number x)

Example:


array A: 1 3 6 7 5 5 2      
x: ------  1 2 3 4 5 6 7 8
tree(x): 1 2 1 3 2 3 1 7
tree(6) = 3 (6 in binary is 110, r=1, 6 - 2^1 + 1 = 5; so tree(6)   stores frequencies for 5 and 6; in our example, number 5 appears 2 times and number 6 appears only once)


But, for the range update - point query i don't know the following: 

a) what tree[x] represents. What is the true meaning for the value that is stored in tree[x] (for range update - point query).

b) To update range, say from a to b with value v, we will do the following operations:


update(a, v)
update(b + 1, -v)
and then query(x) returns value of A[x]

Why does the query(x) returns value of A[x], what is the proof(please give some example or resource with example) for that.


In quest for the answer i found the following resources but none of them helped for the questions above:

1: https://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

2: 
http://apps.topcoder.com/forums/;jsessionid=1749A5CAC2EA52B51F5509E8355A2CD3?module=Thread&amp;threadID=715842&amp;start=0&amp;mc=8#1407869
For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/

The core of BIT is point update - range query, ie. for array $A[1 \dotsc n]$, BIT supports following operations:


$A[k] \leftarrow A[k] + d$ (Point update(k,d))
query partial sum $S[k] = A[1] + A[2] + \dotsb + A[k]$ (Range query(k))


Other variants are just converting to 1 or more of this case.

For range update - point query, it requires support following operations for array $A[1 \dotsc n]$:


$A[i] \leftarrow A[i] + d$ for all $a\le i &lt; b$. (Range update(a,b,d))
query value of $A[k]$. (Point query(k))


First, noting that after range update $A_1[i] \leftarrow A[i] + d, (a \le i \le b)$, we have $$\begin{align}A_1[a]-A_1[a-1]=&amp;A[a]-A[a-1]+d\\A_1[b+1]-A_1[b]=&amp;A[b+1]-A[b]-d\\A_1[i]-A_1[i-1]=&amp;A[i]-A[i-1]\ (i\notin\{a,b+1\})\end{align}$$
Taking $$D[i] = \begin{cases}A[i],&amp;i=1\\A[i]-A[i-1],&amp;1&lt;i\le n\end{cases}$$ then there are only 2 updates $$D[a]\leftarrow D[a]+d\\D[b+1]\leftarrow D[b+1]-d$$ and $$\begin{align}A[k]=&amp;A[1]+(A[2]-A[1])+\dotsb+(A[k]-A[k-1])\\=&amp;D[1]+D[2]+\dotsb+D[k]\end{align}$$

Thus building BIT on $D[1\dotsc n]$, we convert the range update$(a,b,d)$ on $A$ to 2 point updates $(a,d)$ and $(b+1,-d)$ on $D$, and the point query $(k)$ on $A$ is just the range query $(k)$ on $D$.