Массив можно рассматривать как последовательность в порядке двоичного дерева, которое также будет деревом рекурсии, если вы примените наивный алгоритм.
Это двоичное дерево имеет следующие свойства:
Это идеально
Его высота h соответствует количеству двоичных цифр, необходимому дляпредставляют n . Так, в случае 9 (0b1001) ч = 4.
Имеет 2 ч -1 узлы, которые также являются количеством элементов в представлении массива.
Узлы на глубине i дерева, имеют одинаковое значение и соответствуют i th младший значащий бит n . Давайте назовем этот бит n i с i in [1, h ].
Как следствие, общее значение всех узлов вместе является суммой 2 i-1 n i для i в [1, h ], что в точности равно n .
Левое (или правое) поддерево узла на глубине i , будет соответствовать дереву, которое вы получите за этаж (n / 2 i ) .
Чтобы найти узел, соответствующий индексу j (если используется 1), вы должны взять двоичное представление j , используя ровно h двоичных цифр (с добавлением «0», если необходимо), а затемдо тех пор, пока в этом представлении содержится более одной «1», выбирайте левую ветвь, когда крайняя левая цифра равна «0», и правую в противном случае. Затем удалите эту цифру и повторите.
Затем мы могли бы определить, какое значение имеет каждое левое поддерево, которое пропускается при перемещении вправо, включить 1 в сам узел и взять суммуэти ценности. Эта сумма будет представлять количество 1 значений слева индекса j . Это, в свою очередь, может быть использовано, чтобы узнать общее количество значений 1 в любом диапазоне.
Превратившись в алгоритм, вы получите что-то похожее на фрагмент ниже. Вы можете запустить его, ввести значения для n, i, j и просмотреть итоговую сумму:
function sumBetween(n, i, j) {
if (j < i) return sumBetween(n, j, i); // put range in ascending order
return sumUntil(n, j) - sumUntil(n, i - 1);
}
function sumUntil(n, i) {
let numDigits = n.toString(2).length;
let bitMask = 1 << numDigits;
if (i >= bitMask) i = bitMask - 1; // Reduce i when exceeding the "array" size
if (i < 0) i = 0;
let sum = 0;
for (bitMask >>= 1; i > 0 && bitMask > 0; bitMask >>= 1) {
let goRight = i & bitMask; // Extract a bit from i
let nodeValue = n % 2; // Get value at current node of binary tree
n >>= 1; // Go down one level in the tree
if (goRight) sum += nodeValue + n; // Add node value and values in omitted left subtree
i -= goRight; // Clear bit in i
}
return sum;
}
// I/O handling
let inputs = document.querySelectorAll("input");
let result = document.querySelector("span");
document.addEventListener("input", refresh);
function refresh() {
let [n, i, j] = Array.from(inputs, input => input.value).map(Number);
let sum = sumBetween(n, i, j);
result.textContent = sum;
}
refresh();
input { width: 4em }
n: <input type="number" value="9"><br>
i: <input type="number" value="6"><br>
j: <input type="number" value="9"><br>
sum: <span></span>
Алгоритм получения суммы диапазона имеет временную сложность O (logn) , независимо от значенийдля i и j . Сложность пространства составляет O (1) - нет необходимости заполнять массив.