Простой массив префиксов не работает, потому что для поддержки запросов произвольного диапазона требуется, чтобы элементы имели обратное отношение к оператору, например, для добавления обратного является отрицанием, для обратного XOR - сам элемент, для побитового ИЛИ обратного нет.
Двоичное индексированное дерево также не работает по той же причине.
Но куча сбоку работает, за счет хранения от 2 * n до 4 * n элементов (в зависимости от того, сколько добавлено при округлении до степени два), гораздо меньшее расширение, чем 32 * n. Это не сделает наиболее захватывающим использование боковой кучи, но позволит избежать проблем явно связанного дерева: объемных узловых объектов (~ 32 байта на узел) и погони за указателями. Можно использовать обычное неявное двоичное дерево, но это усложняет связь его индексов с индексами в исходном массиве. Боковая куча похожа на полное двоичное дерево, но, по идее, без корня - фактически у нас здесь есть корень, а именно один узел на самом высоком уровне, который хранится. Как и обычное неявное двоичное дерево, боковая куча неявно связана, но правила другие:
left(x) = x - ((x & -x) >> 1)right(x) = x + ((x & -x) >> 1)parent(x) = (x & (x - 1)) | ((x & -x) << 1)
Кроме того, мы можем вычислить некоторые другие вещи, такие как:
leftmostLeaf(x) = x - (x & -x) + 1rightmostLeaf(x) = x + (x & -x) - 1- Самый низкий общий предок двух узлов, но формула немного велика.
Где x & -x можно записать как Integer.lowestOneBit(x).
Арифметика выглядит неясной, но в результате получается такая структура, которую вы можете пройти по арифметике для подтверждения (источник: «Искусство компьютерного программирования», том 4А, побитовые приемы и приемы):
В любом случае мы можем использовать эту структуру следующим образом:
- хранить оригинальные элементы в листьях (нечетные индексы)
- для каждого четного индекса сохраняйте побитовое ИЛИ его дочерних элементов
- для запроса диапазона, вычислите ИЛИ элементов, представляющих диапазон, который не выходит за пределы запрашиваемого диапазона
Для запроса сначала сопоставьте индексы с конечными индексами. Например 1-> 3 и 3-> 7. Затем найдите наименьшего общего предка конечных точек (или просто начните с самого высокого узла) и рекурсивно определите:
rangeOR(i, begin, end):
if leftmostLeaf(i) >= begin and rightmostLeaf(i) <= end
return data[i]
L = 0
R = 0
if rightmostLeaf(left(i)) >= begin
L = rangeOR(left(i), begin, end)
if leftmostLeaf(right(i)) <= end
R = rangeOR(right(i), begin, end)
return L | R
Таким образом, любой узел, соответствующий диапазону, который полностью покрыт , используется целиком В противном случае, если левый или правый дети покрыты на всех , они должны быть рекурсивно опрошены на предмет их вклада, если один из них не охвачен, тогда просто возьмите ноль для этого вклада. Между прочим, я предполагаю, что запрос включает оба конца, поэтому диапазон включает в себя как begin, так и end.
Оказывается, что rightmostLeaf(left(i)) и leftmostLeaf(right(i)) можно значительно упростить, а именно i - (~i & 1) (альтернатива: (i + 1 & -2) - 1) и i | 1 соответственно. Это кажется ужасно асимметричным, хотя. В предположении, что i не является листом (этого не будет в этом алгоритме, поскольку лист либо полностью покрыт, либо вообще не запрошен), они становятся i - 1 и i + 1 соответственно, намного лучше. В любом случае мы можем использовать, чтобы все левые потомки узла имели более низкий индекс, чем он, а все правые потомки имеют более высокий индекс.
Записано на Java это может быть (не проверено):
int[] data;
public int rangeOR(int begin, int end) {
return rangeOR(data.length >> 1, 2 * begin + 1, 2 * end + 1);
}
private int rangeOR(int i, int begin, int end) {
// if this node is fully covered by [begin .. end], return its value
int leftmostLeaf = i - (i & -i) + 1;
int rightmostLeaf = i + (i & -i) - 1;
if (leftmostLeaf >= begin && rightmostLeaf <= end)
return data[i];
int L = 0, R = 0;
// if the left subtree contains the begin, query it
if (begin < i)
L = rangeOR(i - (Integer.lowestOneBit(i) >> 1), begin, end);
// if the right subtree contains the end, query it
if (end > i)
R = rangeOR(i + (Integer.lowestOneBit(i) >> 1), begin, end);
return L | R;
}
Альтернативная стратегия начинается снизу и идет вверх, пока обе стороны не встретятся, и собирает данные по пути вверх. Когда начинается с begin и его родитель находится справа от него, у правого потомка родителя индекс выше, чем у begin, поэтому он является частью запрашиваемого диапазона - если только родитель не был общим предком обоих восходящих " цепи». Например (не проверено):
public int rangeOR(int begin, int end) {
int i = begin * 2 + 1;
int j = end * 2 + 1;
int total = data[i];
// this condition is only to handle the case that begin == end,
// otherwise the loop exit is the `break`
while (i != j) {
int x = (i & (i - 1)) | (Integer.lowestOneBit(i) << 1);
int y = (j & (j - 1)) | (Integer.lowestOneBit(j) << 1);
// found the common ancestor, so done
if (x == y) break;
// if the low chain took a right turn, the right child is part of the range
if (i < x)
total |= data[x + (Integer.lowestOneBit(x) >> 1)];
// if the high chain took a left turn, the left child is part of the range
if (j > y)
total |= data[y - (Integer.lowestOneBit(y) >> 1)];
i = x;
j = y;
}
return total;
}
Построение дерева в первую очередь не тривиально, построение его в порядке возрастания индексов не работает. Он может быть построен уровень за уровнем, начиная с нижней части. Более высокие узлы касаются рано (например, для первого слоя шаблон 2, 4, 6, в то время как 4 находится во втором слое), но они все равно будут перезаписаны, хорошо временно оставить там неконечное значение.
public BitwiseORRangeTree(int[] input) {
// round length up to a power of two, then double it
int len = input.length - 1;
len |= len >> 1;
len |= len >> 2;
len |= len >> 4;
len |= len >> 8;
len |= len >> 16;
len = (len + 1) * 2;
this.data = new int[len];
// copy input data to leafs, odd indexes
for (int i = 0; i < input.length; i++)
this.data[i * 2 + 1] = input[i];
// build higher levels of the tree, level by level
for (int step = 2; step < len; step *= 2) {
for (int i = step; i < this.data.length; i += step) {
this.data[i] = this.data[i - (step >> 1)] | this.data[i + (step >> 1)];
}
}
}