Дерево Фенвика (Binary Indexed Tree) для префиксных сумм. Прибавление к элементу и сумма на отрезке — O(log n), построение — O(n). Компактнее и быстрее SegmentTree, но поддерживает только обратимые операции (сумму).
Отрезки задаются полуинтервалом [from, to).
[from, to)
const sums = new FenwickTree([3, 1, 4, 1, 5]);sums.rangeSum(1, 4); // 1 + 4 + 1 = 6sums.add(2, 10);sums.prefixSum(3); // 3 + 1 + 14 = 18 Copy
const sums = new FenwickTree([3, 1, 4, 1, 5]);sums.rangeSum(1, 4); // 1 + 4 + 1 = 6sums.add(2, 10);sums.prefixSum(3); // 3 + 1 + 14 = 18
Длина массива из нулей или исходные значения.
Прибавляет delta к элементу index.
delta
index
Устанавливает значение элемента.
Значение элемента.
Сумма первых count элементов, то есть отрезка [0, count).
count
[0, count)
Сумма на полуинтервале [from, to).
Дерево Фенвика (Binary Indexed Tree) для префиксных сумм. Прибавление к элементу и сумма на отрезке — O(log n), построение — O(n). Компактнее и быстрее SegmentTree, но поддерживает только обратимые операции (сумму).
Отрезки задаются полуинтервалом
[from, to).Example