Я просмотрел несколько руководств по обновлению Range - запросы диапазона двоичного индексированного дерева. Я не могу понять ни одного из них. Я не понимаю необходимость создания другого дерева.
Может ли кто-нибудь объяснить это мне на простом английском языке с примером?
Попытка объяснить более интуитивно (как я понял). Я разберу его в четыре этапа:
Предположим, что обновление находится между A и B с V, а запрос является префиксом для любого индекса <= X
Первое - это простое дерево обновлений/дерева запросов. Когда вы обновляете A до B с помощью V, на практике вы добавляете V в позицию A, поэтому на него влияет любой префиксный запрос X >= A. Затем вы удаляете V из B + 1, поэтому любой запрос X >= B + 1 не видит добавленного V к A. Никаких сюрпризов здесь.
T1.sum(X) - это точечный запрос к этому первому дереву в X. Мы с оптимизмом предполагаем, что каждый элемент до X равен значению в X. Вот почему мы делаем T1.sum(X)*X. Очевидно, это не совсем правильно, поэтому мы:
При обновлении диапазона мы также обновляем второе дерево, чтобы указать, сколько мы должны исправить первый запрос T1.sum(X)*X. Это обновление состоит в удалении (A-1)*V из любого запроса X >= A. Затем добавим обратно B*V для X >= B. Мы делаем последнее, потому что запросы к первому дереву не возвращают V для X >= B + 1 (из-за T1.add(B+1, -V)), поэтому нам нужно как-то сказать, что для любого запроса есть прямоугольник области (B-A+1)*V Х >= В + 1. Мы уже удалили (A-1)*V из A, нам нужно добавить обратно 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)
Позвольте мне попытаться объяснить это.
Зачем нам нужно второе дерево? Я не могу ответить на этот вопрос. Строго говоря, я не могу доказать, что решить эту проблему невозможно, используя только одно дерево двоичных индексов (и я никогда не видел такого доказательства нигде).
Как можно придумать этот метод? Опять же, я не знаю. Я не изобретатель этого алгоритма. Поэтому я не могу понять, почему это выглядит так. Единственное, что я попытаюсь объяснить, - это то, почему и как работает этот метод.
Чтобы лучше понять этот алгоритм, первое, что мы должны сделать, - это забыть о том, как работает дерево двоичных индексов. Позвольте рассматривать это как черный ящик, поддерживающий две операции: обновить один элемент и выполнить запрос суммы диапазона в O(log n) время. Мы просто хотим использовать один или несколько таких "черных ящиков" для создания структуры данных, которая может эффективно выполнять обновления диапазона и запросы.
Мы будем поддерживать два двоичных дерева индексов: T1 и T2. Я буду использовать следующие обозначения: T.add(pos, delta) для выполнения обновления точки в позиции pos значением delta и 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) за запрос.
Я потратил много дней, чтобы понять обновление диапазона, написал простое объяснение с примером здесь: https://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md