Need a clear explanation of Range updates and range queries Binary indexed tree

Question

I have gone through few tutorials of Range update - Range queries of Binary indexed tree. I'm unable to understand any of them. I don't understand the need of building another tree.

Could someone explain it to me in plain English with an example?

Answer 1

Trying to explain in more intuitive way (the way I understood). I'll divide it in four steps:

Assume the update is between A and B with V and the query is a prefix query for any index <=X

The first range update/point query tree (T1)

The first is a simple range update/point query tree. When you update A to B with V, in practice you add V to position A, so any prefix query X>=A is affected by it. Then you remove V from B+1, so any query X >= B+1 doesn't see the V added to A. No surprises here.

Prefix query to the range update/point tree

The T1.sum(X) is a point query to this first tree at X. We optimistically assume then that every element before X is equal to the value at X. That's why we do T1.sum(X)*X. Obviously this isn't quite right, that's why we:

Use a modified range update/point query tree to fix the result (T2)

When updating the range, we also update a second tree to tell how much we have to fix the first T1.sum(X)*X query. This update consists in removing (A-1)*V from any query X>=A. Then we add back B*V for X>=B. We do the latter because queries to the first tree won't return V for X>=B+1 (because of the T1.add(B+1, -V)), so we need to somehow tell that there is a rectangle of area (B-A+1)*V for any query X>=B+1. We already removed (A-1)*V from A, we only need to add back B*V to B+1.

Wrapping it all together

update(A, B, V):
    T1.add(A, V)         # add V to any X>=A
    T1.add(B+1, -V)      # cancel previously added V from any X>=B+1

    T2.add(A, (A-1)*V)   # add a fix for (A-1)s V that didn't exist before A
    T2.add(B+1, -B*V)    # remove the fix, and add more (B-A+1)*V to any query 
                         # X>=B+1. This is really -(A-1)*V -(B-A+1)*V, but it 
                         # simplifies to -B*V

sum(X):
    return T1.sum(X)*X - T2.sum(X)

Answer 2

Let me try to explain it.

1. Why do we need a second tree? I cannot answer this question. Strictly speaking, I cannot prove that it is impossible to solve this problem using only one binary index tree(and I have never seen such a proof anywhere).

2. How can one come up with this method? Again, I don't know. I'm not the inventor of this algorithm. So I cannot tell why does it look exactly like this. The only thing I will try to explain is why and how this method works.

3. To understand this algorithm better, the first we should do is to forget about how the binary index tree itself works. Let's treat it as just a black box that supports two operations: update one element and perform a range sum query in O(log n) time. We just want to use one or more such "black boxes" to build a data structure that can perform range updates and queries efficiently.

4. We will maintain two binary index trees: T1 and T2. I will use the following notation: T.add(pos, delta) for performing a point update in a position pos by delta value and T.get(pos) for a sum [0 ... pos]. I claim that if an update function looks like this:

   void update(left, right, delta)
       T1.add(left, delta)
       T1.add(right + 1, -delta);
       T2.add(left, delta * (left - 1))
       T2.add(right + 1, -delta * right);
   

   and a range query is answered this way(for a prefix [0 ... pos]):

   int getSum(pos)
       return T1.sum(pos) * pos - T2.sum(pos)
   

   then the result is always correct.

5. To prove its correctness, I will prove the following statement: each update changes the answer appropriately(it gives a proof by induction for all operations, because initially everything is filled with zeros and the correctness is obvious). Let's assume that we had a left, right, DELTA update and now we are performing pos query(that is, 0 ... pos sum). Let's consider 3 cases:
   i) pos < L. The update does not affect this query. The answer is correct(due to the induction hypothesis).
   ii) L <= pos <= R. This update will add DELTA * pos - (left - 1) * pos. It means that DELTA is added pos - L + 1 times. That's exactly how it should be. Thus, this case is also handled correctly.
   iii) pos > R. This update will add 0 + DELTA * right - DELTA * (left - 1). That is, DELTA is added exactly right - left + 1 times. It is correct, too.

   We have just shown the correctness of the induction step. Thus, this algorithm is correct.

6. I have only shown how to answer [0, pos] sum queries. But answering [left, right] query is easy now: it is just getSum(right) - getSum(left - 1).

That's it. I have shown that this algorithm is correct. Now let's try to code it and see if it works(it is just a sketch, so the code quality might be not really good):

#include <bits/stdc++.h>

using namespace std;

// Binary index tree.
struct BIT {
  vector<int> f;

  BIT(int n = 0) {
    f.assign(n, 0);
  }

  int get(int at) {
    int res = 0;
    for (; at >= 0; at = (at & (at + 1)) - 1)
      res += f[at];
    return res;
  }

  void upd(int at, int delta) {
    for (; at < f.size(); at = (at | (at + 1)))
      f[at] += delta;
  }
};

// A tree for range updates and queries.
struct Tree {
  BIT f1;
  BIT f2;

  Tree(int n = 0): f1(n + 1), f2(n + 1) {}

  void upd(int low, int high, int delta) {
    f1.upd(low, delta);
    f1.upd(high + 1, -delta);
    f2.upd(low, delta * (low - 1));
    f2.upd(high + 1, -delta * high);
  }

  int get(int pos) {
    return f1.get(pos) * pos - f2.get(pos);
  }

  int get(int low, int high) {
    return get(high) - (low == 0 ? 0 : get(low - 1));
  }
};

// A naive implementation.
struct DummyTree {
  vector<int> a;

  DummyTree(int n = 0): a(n) {}

  void upd(int low, int high, int delta) {
    for (int i = low; i <= high; i++)
      a[i] += delta;
  }

  int get(int low, int high) {
    int res = 0;
    for (int i = low; i <= high; i++)
      res += a[i];
    return res;
  }
};

int main() {
  ios_base::sync_with_stdio(0);
  int n = 100;
  Tree t1(n);
  DummyTree t2(n);
  for (int i = 0; i < 10000; i++) {
    int l = rand() % n;
    int r = rand() % n;
    int v = rand() % 10;
    if (l > r)
      swap(l, r);
    t1.upd(l, r, v);
    t2.upd(l, r, v);
    for (int low = 0; low < n; low++)
      for (int high = low; high < n; high++)
    assert(t1.get(low, high) == t2.get(low, high));
  }
  return 0;
}

Oh, yeah. I forgot about time complexity analysis. But it is trivial here: we make a constant number of queries to binary index tree, thus it is O(log n) per query.

Answer 3

I have spent many days to understand range update, wrote simple explanation with example here: https://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md