我已经阅读了一些范围更新的教程 - 二进制索引树的范围查询。我无法理解其中任何一个。我不明白建造另一棵树的必要性。
有人可以用简单的英语向我解释一下吗？
问问题
2909 次
3 回答
10
尝试以更直观的方式（我理解的方式）进行解释。我将它分为四个步骤：
假设更新是在 A 和 B 之间使用 V 并且查询是任何索引 <=X 的前缀查询
第一个范围更新/点查询树 (T1)
第一个是简单的范围更新/点查询树。当您使用 V 将 A 更新为 B 时，实际上您将 V 添加到位置 A，因此任何前缀查询 X>=A 都会受到它的影响。然后从 B+1 中删除 V，因此任何查询 X >= B+1 都不会看到 V 添加到 A。这并不奇怪。
范围更新/点树的前缀查询
这T1.sum(X)是对 X 处的第一棵树的点查询。我们乐观地假设 X 之前的每个元素都等于 X 处的值。这就是我们这样做的原因T1.sum(X)*X。显然这并不完全正确，这就是为什么我们：
使用修改后的范围更新/点查询树来修复结果 (T2)
更新范围时，我们还会更新第二棵树，以告知我们必须修复第一个T1.sum(X)*X查询的程度。此更新包括(A-1)*V从任何查询中删除 X>=A。然后我们加回B*VX>=B。我们这样做是因为对第一棵树的查询不会返回 V for X>=B+1（因为），所以我们需要以某种方式告诉任何查询 X>=B+1T1.add(B+1, -V)都有一个矩形区域(B-A+1)*V. 我们已经(A-1)*V从 A 中删除了，我们只需要添加回B*VB+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)
于 2015-01-10T14:44:37.407 回答
2
让我试着解释一下。
为什么我们需要第二棵树？我无法回答这个问题。严格来说，我无法证明只使用一个二叉索引树是不可能解决这个问题的（而且我从未在任何地方看到过这样的证明）。
怎么能想出这种方法？再说一次，我不知道。我不是这个算法的发明者。所以我不知道为什么它看起来完全像这样。我将尝试解释的唯一一件事是这种方法为什么以及如何工作。
为了更好地理解这个算法，我们首先应该忘记二叉索引树本身是如何工作的。让我们把它当作一个黑盒子，它支持两种操作：更新一个元素和及时执行范围求和查询
O(log n)。我们只是想使用一个或多个这样的“黑匣子”来构建一个可以高效执行范围更新和查询的数据结构。我们将维护两个二叉索引树：
T1和T2。我将使用以下符号：按值T.add(pos, delta)在位置执行点更新和求和。我声称如果更新函数如下所示：posdeltaT.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。更新不会影响此查询。答案是正确的（由于归纳假设）。
二）L <= pos <= R。本次更新将添加DELTA * pos - (left - 1) * pos. 意思DELTA是加倍pos - L + 1。这正是它应该的样子。因此，这种情况也得到了正确处理。
三）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)每个查询。
于 2015-01-10T12:35:55.507 回答
1
我花了很多天来了解范围更新，在这里用示例写了简单的解释： https ://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md
于 2017-11-05T02:13:00.480 回答