Нужно четкое объяснение обновлений Range и запросов диапазона. Двоичное индексированное дерево

Я просмотрел несколько руководств по обновлению Range - запросы диапазона двоичного индексированного дерева. Я не могу понять ни одного из них. Я не понимаю необходимость создания другого дерева.

Может ли кто-нибудь объяснить это мне на простом английском языке с примером?

Ответы

Ответ 1

Попытка объяснить более интуитивно (как я понял). Я разберу его в четыре этапа:

Предположим, что обновление находится между A и B с V, а запрос является префиксом для любого индекса <= X

Первое дерево обновления диапазона/точечного запроса (T1)

Первое - это простое дерево обновлений/дерева запросов. Когда вы обновляете 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. Очевидно, это не совсем правильно, поэтому мы:

Использовать модифицированное дерево изменения/дерева запросов для исправления результата (T2)

При обновлении диапазона мы также обновляем второе дерево, чтобы указать, сколько мы должны исправить первый запрос 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)

Ответ 2

Позвольте мне попытаться объяснить это.

  • Зачем нам нужно второе дерево? Я не могу ответить на этот вопрос. Строго говоря, я не могу доказать, что решить эту проблему невозможно, используя только одно дерево двоичных индексов (и я никогда не видел такого доказательства нигде).

  • Как можно придумать этот метод? Опять же, я не знаю. Я не изобретатель этого алгоритма. Поэтому я не могу понять, почему это выглядит так. Единственное, что я попытаюсь объяснить, - это то, почему и как работает этот метод.

  • Чтобы лучше понять этот алгоритм, первое, что мы должны сделать, - это забыть о том, как работает дерево двоичных индексов. Позвольте рассматривать это как черный ящик, поддерживающий две операции: обновить один элемент и выполнить запрос суммы диапазона в 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) за запрос.