[Solved]: BIT: range updates, point queries; true meaning of tree[x]

Problem Detail: 

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:

1. let tree be an array where we represent our BIT
2. 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&threadID=715842&start=0&mc=8#1407869

Asked By : user2555240

Answered By : Terence Hang

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:

1. $A[k] \leftarrow A[k] + d$ (Point update(k,d))
2. 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]$:

1. $A[i] \leftarrow A[i] + d$ for all $a\le i < b$. (Range update(a,b,d))
2. 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]=&A[a]-A[a-1]+d\\A_1[b+1]-A_1[b]=&A[b+1]-A[b]-d\\A_1[i]-A_1[i-1]=&A[i]-A[i-1]\ (i\notin\{a,b+1\})\end{align}$$ Taking $$D[i] = \begin{cases}A[i],&i=1\\A[i]-A[i-1],&1<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]=&A[1]+(A[2]-A[1])+\dotsb+(A[k]-A[k-1])\\=&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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47273

3.2K people like this

 Download Related Notes/Documents