A segment tree is a binary tree over array segments. It supports range queries (sum/min/max) and point updates in O(log n) after an O(n) build. With lazy propagation it can handle range updates too.
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];
}
}