Использование двоичных индексированные деревьев для расширения RMQ

Question

RMQ problem может быть расширен следующим образом:

Учитывая это массив целых чисел nA.

запроса (х, у): даны два целых числа 1 ≤ x, y ≤ n, найти минимум A[x], A[x+1], ... A[y];

обновление (х, у): дано целое число v и 1 ≤ x ≤ n делают A[x] = v.

Эта проблема может быть решена в O(log n) для обеих операций с использованием segment trees.

Это эффективное решение на бумаге, но на практике сегментные деревья содержат много накладных расходов, особенно если они реализованы рекурсивно.

Я знаю, что существует способ решить проблему в O(log^2 n) для одного (или обоих, я не уверен) операций, используя двоичные индексированные деревья (можно найти больше ресурсов, но this и this, IMO, самые сжатые и исчерпывающие, соответственно). Это решение для значений n, которые вписываются в память, на практике быстрее, потому что у BIT намного меньше накладных расходов.

Однако я не знаю, как структура BIT используется для выполнения данных операций. Я знаю только, как использовать его для запроса суммы интервала, например. Как я могу использовать его, чтобы найти минимум?

Если это помогает, у меня есть код, написанный другими, который делает то, о чем я прошу, но я не могу понять это. Вот один такой кусок кода:

int que(int l, int r) { 
    int p, q, m = 0; 

    for(p=r-(r&-r); l<=r; r=p, p-=p&-p) { 
     q = (p+1 >= l) ? T[r] : (p=r-1) + 1; 
     if(a[m] < a[q]) 
      m = q; 
    } 

    return m; 
} 

void upd(int x) { 
    int y, z; 
    for(y = x; x <= N; x += x & -x) 
     if(T[x] == y) { 
      z = que(x-(x&-x) + 1, x-1); 
      T[x] = (a[z] > a[x]) ? z : x; 
     } 
     else 
      if(a[ T[x] ] < a[ y ]) 
       T[x] = y; 
} 

В приведенном выше коде, T инициализируется 0, a является данный массив, N его размер (они индексацию с 1 по какой-либо причине) и upd вызывается в сначала для каждого значения чтения. До того, как upd называется a[x] = v.

Кроме того, p & -p - это то же самое, что и p^(p & (p - 1)) в некоторых источниках BIT, и индексирование начинается с 1 с нулевым элементом, инициализированным до бесконечности.

Может ли кто-нибудь объяснить, как это работает, или как я могу решить данную проблему с помощью BIT?

Answer 1

От уровня выше бита пустячный, это то, что мы имеем:

нормальный битовый массив g для массива данных целочисленного a хранит в диапазоне сумм.

g[k] = sum{ i = D(k) + 1 .. k } a[i] 

D(k) где только k с битом низшего порядка 1 равен 0. Здесь мы имеем вместо

T[k] = min{ i = D(k) + 1 .. k } a[i] 

Запрос работает точно так же, как нормальный диапазон BIT суммы запроса с изменением, что минимумами поддиапазонов принимается по мере продолжения запроса, а не сумм. Для N элементов в a в N есть биты потолка (log N), которые определяют время выполнения.

Обновление требует больше работы, поскольку изменения в O (log N) минимальны - то есть элементы g - зависят от изменения, и каждый из них сам выполняет запрос O (log N). Это делает обновление O (log^2 n) в целом.

На уровне бит-бит это чудовищно умный код. Оператор x += x & -x удаляет последовательную строку нижнего порядка из 1 в x, а затем устанавливает следующий нулевой уровень высшего порядка 1. Это именно то, что вам нужно, чтобы «пересечь» BIT для исходного целого числа x.

Answer 2

Сегментные деревья - эффективное решение на практике. Однако вы не реализуете их как деревья. Раунд n до следующей мощности двух и использовать массив rmq размера 2*n. Последние n записей rmq: A. Если j < n, то rmq[j] = min(rmq[2*j], rmq[2*j+1]). Вам нужно только просмотреть логарифмически много записей rmq, чтобы ответить на запрос минимального диапазона. И вам нужно обновить логарифмически много записей rmq при обновлении записи A.

Я не понимаю ваш код, так что я не собираюсь это замечать.

Answer 3

Я не смотрел на код в деталях, но это, кажется, примерно соответствует следующей схеме:

1) Keep структуру BIT, то есть наложить древовидную структуру на основе полномочий из двух в массиве.

2) В каждом узле дерева сохраняйте минимальное значение, найденное у любого потомка этого узла.

3) Учитывая произвольный диапазон, поставьте указатели в начале и конце диапазона и перемещайте их вверх, пока они не совпадут. Если вы переместите указатель вверх и в направлении другого указателя, вы только что ввели узел, в котором каждый потомок является членом диапазона, поэтому обратите внимание на это значение на этом узле. Если вы перемещаете указатель вверх и в сторону от другого указателя, узел, с которым вы только что присоединились, записывает минимум, полученный из значений, включая значения вне диапазона, и вы уже учли каждое соответствующее значение ниже этого узла внутри диапазона, поэтому игнорируйте значение на этом узле.

4) Как только два указателя являются одним и тем же указателем, минимальное значение в этом диапазоне является минимальным значением в любом узле, который вы приняли к сведению.