Обе структуры решают задачу: «есть массив, его элементы меняются; нужно быстро считать агрегат на отрезке». Наивный подход требует O(n) на каждый запрос, а эти структуры отвечают за O(log n).
Отрезки задаются полуинтервалом [from, to), как в Array#slice:
query(1, 4) охватывает индексы 1, 2 и 3.
Работает с любой ассоциативной операцией, то есть такой, для которой
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). Нужно передать саму операцию и её нейтральный элемент.
import { SegmentTree } from 'ds-kit-js';
const temps = SegmentTree.max([12, 18, 15, 21, 9, 14]);
temps.query(0, 3); // 18 — максимум за первые три дня
temps.set(1, 25);
temps.query(0, 3); // 25
// Готовые фабрики: SegmentTree.sum, SegmentTree.min, SegmentTree.max.
// Собственная операция — например, НОД:
const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
const tree = new SegmentTree([12, 18, 24, 36], gcd, 0);
tree.query(1, 4); // 6
Операция не обязана быть коммутативной: порядок элементов сохраняется. Поэтому подходят, например, конкатенация строк или умножение матриц.
Специализированная структура только для сумм. Она проще, быстрее и занимает вдвое меньше памяти, чем дерево отрезков.
import { FenwickTree } from 'ds-kit-js';
// Продажи по дням
const sales = new FenwickTree([120, 80, 200, 150, 90]);
sales.rangeSum(1, 4); // 80 + 200 + 150 = 430
sales.add(2, 50); // день 2: +50
sales.prefixSum(3); // 120 + 80 + 250 = 450
sales.set(0, 0);
new FenwickTree(1000); // массив из 1000 нулей