Дерево Фенвика

Дерево Фенвика - структура данных, позволяющая считать xor, sum и другие операции на любом подотрезке с изменениями. Также ее легко обобщить на большие размерности.

Описание работы алгоритма

Создадим массив, который будет строиться таким образом, в ячейке $a rr [i]$ будет лежать сумма на отрезке $[F (i), i]$ . Популярны 2 функции:

$F (x) =$ x & (x + 1)
$F (x) =$ x - (x & -x) + 1

В общем первая версия функции более популярна, но менее функциональна, разбираться в ее работе мне лень и я ее опущу. Вторая функция за свою операцию обнуляет последний бит двоичной записи числа. Чтобы это понять, нужно знать, что отрицательные числа в c++ хранятся по модулю $2^{32}$ или $2^{64}$ , и x c -x должны в сумме давать 0, а значит, у них на месте последней единицы биты совпадают, правее все биты различаются, левее же они равны 0. Теперь, чтобы посчитать значение функции на любом отрезке, мы считаем ее на двух префиксах за $O (lo g_{2} n)$ , а потом пользуясь обратимостью высчитываем результат на отрезке. Изменение элемента затрагивает только некоторые отрезки поймем как их обновить за $O (lo g_{2} n)$ .

Утверждение. Следующий элемент содержащий x, это x + (x & -x), также он содержит и весь отрезок x.

Доказательство. Пусть y - искомое нами число, что мы про него знаем? Мы знаем, что если обнулить последнюю 1 в двоичной записи y, то он станет меньше чем x, а значит до этого бита x и y полностью совпадают, из чего следует, что раз раньше было верно $y > x$ , а теперь $y < x$ то в x на этой позиции находится 0, иначе до обнуления x был бы больше или равен y, что невозможно. Также верно, что после этого бита в записи x есть хотя бы одна 1. Раз мы ищем минимально возможное y, то возьмем последний подотрезок 1 в записи x, до него в записи как раз и присутствует бит, который равен 0 в x, а значит подходит нам. Как мы уже выяснили (x & -x) - это наименьший бит, равный 1. После его добавлении к x и ряда переходов мы и получим наименьший y. Он содержит весь отрезок x, потому что после удаления нашего последнего единичного бита после него все в записи y равно 0, в x же на этом подотрезке есть хотя бы одна единица, а значит после выполнения преобразования с ним мы не получим числа меньше.

Так что обновление происходит так же, как и подсчет ответа и работает за $O (lo g_{2} n)$ .

Код

Весь код состоит из двух функций sum и change, которые и выполняют описанный выше алгоритм.

long long sum(long long x) {
  long long ans = 0;
  while (x) {
    ans += f[x];
    x -= x & -x;
  }
  return ans;
}
 
long long sum(long long l, long long r) {
  return sum(r) - sum(l - 1);
}
 
void change(long long x, long long ind) {
  while (ind < f.size()) {
    f[ind] += x;
    ind += ind & -ind;
  }
}

Многомерные случаи

Плюс Фенвика заключается в том, что он очень просто обобщается на многомерные случаи, для этого мы просто увеличивает размерность массива, а также добавляем циклы. Изменения лучше сделать только в подсчете функции, ведь для этого нужно определить $2^{k}$ коэффициентов, где $k$ - наша размерность и это проще писать не вручную, а с помощью такого перебора:

long long sum(long long x1, long long x2, long long y1, long long y2, long long z1, long long z2) {
  vector<long long> x_c, y_c, z_c;
  x_c.push_back(x2);
  x_c.push_back(x1 - 1);
  y_c.push_back(y2);
  y_c.push_back(y1 - 1);
  z_c.push_back(z2);
  z_c.push_back(z1 - 1);
  long long ans = 0;
  for (long long x_ind = 0; x_ind < 2; x_ind++) {
    for (long long y_ind = 0; y_ind < 2; y_ind++) {
      for (long long z_ind = 0; z_ind < 2; z_ind++) {
        if (x_ind ^ y_ind ^ z_ind) {
          ans -= sum(x_c[x_ind], y_c[y_ind], z_c[z_ind]); 
        } else {
          ans += sum(x_c[x_ind], y_c[y_ind], z_c[z_ind]);
        }
      }
    }
  }
  return ans;
}

Максимум и минимум

Одним из узких мест дерева Фенвика является обязательная обратимость функции, которой обладают всего лишь некоторые функции. Тем не менее, для подсчета максимума и минимума были придуманы небольшие улучшения Фенвика, которые позволяют считать их также за $O (lo g_{2} n)$ , но только если изменения улучшают ответ, в частности для максимума все изменения увеличивают массив, а для минимума уменьшают.

Утверждение. Числа x + (x & -x) и x - (x & -x) содержат отрезки, по длине большие, чем x.

Доказательство. Как мы знаем, длина отрезка x равна $2^{k}$ , где k - позиция последней 1 в записи x. Так как в обоих числах x + (x & -x) и x - (x & -x) номер последнего бита, равного 1, больше, чем у x, значит и отрезки, хранящиеся в них больше.

Теперь давайте насчитаем 2 массива left и right вместо одного, в одном все отрезки будут направлены обычно, а в другом в противоположную сторону. Тогда пусть нам надо посчитать ответ на отрезке от l до r, давайте запустим движение по right от l и будем прыгать, если отрезок не выходит за r. То же самое мы запустим и от r, но с массивом left.

Утверждение. Эти алгоритмы закончат работу в одном элементе.

Доказательство. Пусть это не так и первый алгоритм закончил работу в элементе $f_{l}$ , а второй в $f_{r}$ . Если их отрезки разной длины, то из той, у которой отрезок меньше, можно прыгнуть, ведь как мы уже доказывали, прыжок из вершины происходит в наиближайшую, у которой длина больше, чем у данной вершины. Если же длины $f_{l}$ и $f_{r}$ совпадают, то между ними обязательно должна находиться вершина, с длиной, большей чем у них, ведь $f_{l} + (f_{l} \land - f_{l})$ не может превысить $f_{r}$ .

Раз алгоритм закончит работу в одном элементе, то нам достаточно его дважды запустить и также учесть этот самый элемент. Обновление также надо производить сразу в двух массивах, но в остальном оно полностью аналогично стандартному.

Примечание

Не советую писать это для такой задачи, ведь это чуть лучше дерева отрезков в плане скорости выполнения операций, а также это накладывает сильные ограничения на операцию изменения, но как идея этот алгоритм заслуживает внимания.

Notes

Explorer

Дерево Фенвика

Описание работы алгоритма

Код

Многомерные случаи

Максимум и минимум

Примечание

Graph View

Backlinks