Segment tree to drzewo binarne nad przedziałami tablicy. Umożliwia zapytania zakresowe (suma/min/max) i aktualizacje punktowe w O(log n) po zbudowaniu w O(n). Z lazy propagation potrafi też obsługiwać aktualizacje zakresowe.
class SegTree {
private tree: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.tree = Array(4 * n).fill(0);
}
update(node: number, l: number, r: number, idx: number, val: number) {
if (l === r) {
this.tree[node] = val;
return;
}
const mid = Math.floor((l + r) / 2);
if (idx <= mid) this.update(node * 2, l, mid, idx, val);
else this.update(node * 2 + 1, mid + 1, r, idx, val);
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
}Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce:
Poniżej dodatkowy przykład (bazuje na tym, co już jest w odpowiedzi):
class SegTree {
private tree: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.tree = Array(4 * n).fill(0);
}
update(node: number, l: number, r: number, idx: number, val: number) {
if (l === r) {
this.tree[node] = val;
return;
}
const mid = Math.floor((l + r) / 2);
if (idx <= mid) this.update(node * 2, l, mid, idx, val);
else this.update(node * 2 + 1, mid + 1, r, idx, val);
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
}