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