需要清楚解释范围更新和范围查询二叉索引树

Question

我已经完成了范围更新的几个教程 - 二叉索引树的范围查询。我无法理解其中任何一个。我不明白建造另一棵树的必要性。

谁能用通俗易懂的英语举例说明一下？

Answer 1

让我试着解释一下。

为什么我们需要第二棵树？我无法回答这个问题。严格来说，我无法证明仅使用一棵二叉索引树无法解决此问题（而且我从未在任何地方见过这样的证明）。
怎么想出这种方法的？再一次，我不知道。我不是这个算法的发明者。所以我不知道为什么它看起来完全像这样。我将尝试解释的唯一一件事是为什么以及如何使用此方法。
为了更好地理解这个算法，首先我们应该忘记二叉索引树本身是如何工作的。我们把它当作一个黑盒子，支持两种操作：更新一个元素和在 O(log n) 时间内执行范围求和查询。我们只是想使用一个或多个这样的"black boxes"来构建一个可以高效执行范围更新和查询的数据结构。
我们将维护两个二叉索引树：T1和T2。我将使用以下表示法：T.add(pos, delta) 用于通过 delta 值在位置 pos 执行点更新，而 T.get(pos) 用于总和 [0 ... pos]。我声称如果更新函数如下所示：
```
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);
```
并以这种方式回答范围查询（对于前缀 [0 ... pos]）：
```
int getSum(pos)
    return T1.sum(pos) * pos - T2.sum(pos)
```
那么结果总是正确的。
为了证明其正确性，我将证明以下陈述：每次更新都会适当地更改答案（它通过归纳法为所有操作提供了证明，因为最初一切都用零填充并且正确性是明显的）。假设我们有一个 left, right, DELTA 更新，现在我们正在执行 pos 查询（即 0 ... pos sum）。让我们考虑 3 种情况：
i) pos < L。此更新不会影响此查询。答案是正确的（由于归纳假设）。
ii) L <= pos <= R。此更新将添加 DELTA * pos - (left - 1) * pos。这意味着 DELTA 被添加 pos - L + 1 次。这正是它应该如何。因此，这种情况也得到了正确的处理。
iii) pos > R。此更新将添加 0 + DELTA * right - DELTA * (left - 1)。也就是说，DELTA 恰好添加了 right - left + 1 次。也是对的。

我们刚刚展示了归纳步骤的正确性。因此，这个算法是正确的。
我只展示了如何回答 [0, pos] 求和查询。但是现在回答 [left, right] 查询很容易：它只是 getSum(right) - getSum(left - 1)。

就是这样。我已经证明这个算法是正确的。现在让我们尝试编写代码，看看它是否有效（这只是一个草图，所以代码质量可能不是很好）：

#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;
}

哦，是的。我忘记了时间复杂度分析。但这在这里很简单：我们对二叉索引树进行恒定数量的查询，因此每个查询 O(log n)。

Answer 2

尝试以更直观的方式（我理解的方式）进行解释。我将其分为四个步骤：

假设更新是在A和B之间用V进行的，查询是任何索引<=X

的前缀查询

第一个范围update/point查询树(T1)

第一个是简单的范围update/point查询树。当你用 V 更新 A 到 B 时，实际上你将 V 添加到位置 A，所以任何前缀查询 X>=A 都会受到它的影响。然后从 B+1 中删除 V，因此任何查询 X >= B+1 都不会看到添加到 A 的 V。这里没有惊喜。

前缀查询范围update/point树

T1.sum(X) 是对 X 处第一棵树的点查询。我们乐观地假设 X 之前的每个元素都等于 X 处的值。那是为什么我们这样做 T1.sum(X)*X。显然这不太正确，这就是为什么我们：

使用修改范围 update/point 查询树修复结果 (T2)

更新范围时，我们还更新了第二棵树，以告知我们必须修复第一个 T1.sum(X)*X 查询的程度。此更新包括从任何查询 X>=A 中删除 (A-1)*V。然后我们为 X>=B 添加回 B*V。我们做后者是因为对第一棵树的查询不会 return V for X>=B+1（因为 T1.add(B+1, -V)），所以我们需要以某种方式告诉有一个矩形区域(B-A+1)*V 对于任何查询 X>=B+1。我们已经从 A 中删除了 (A-1)*V，我们只需要将 B*V 添加回 B+1。

全部打包

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 3

我花了很多天来了解范围更新，在这里写了简单的解释和例子： https://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md

需要清楚解释范围更新和范围查询二叉索引树

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

algorithm

data-structures

fenwick-tree

第一个范围update/point查询树(T1)

前缀查询范围update/point树

使用修改范围 update/point 查询树修复结果 (T2)

全部打包