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

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

Предположим, что обновление находится между 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 для любого запроса X›=B +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)

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

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

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

3. Чтобы лучше понять этот алгоритм, первое, что мы должны сделать, это забыть о том, как работает само дерево бинарных индексов. Давайте рассматривать его как просто черный ящик, который поддерживает две операции: обновить один элемент и выполнить запрос суммы диапазона за O(log n) время. Мы просто хотим использовать один или несколько таких «черных ящиков» для создания структуры данных, которая может эффективно выполнять обновления диапазона и запросы.

4. Мы будем поддерживать два дерева бинарных индексов: 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)
   

   тогда результат всегда правильный.

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

   Мы только что показали корректность шага индукции. Таким образом, этот алгоритм является правильным.

6. Я только показал, как отвечать на [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) за запрос.

Я потратил много дней, чтобы понять обновление диапазона, написал простое объяснение с примером здесь: ://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md