Дерево отрезков

1class SegmentTree {
2  private n: number
3  private sum: number[] // узел i покрывает диапазон
4 
5  constructor(values: number[]) {
6    this.n = values.length
7    this.sum = new Array(2 * this.n).fill(0)
8    for (let i = 0; i < this.n; i++) this.sum[this.n + i] = values[i]!
9    for (let i = this.n - 1; i > 0; i--) {
10      this.sum[i] = this.sum[2 * i]! + this.sum[2 * i + 1]!
11    }
12  }
13 
14  rangeSum(l: number, r: number): number { // [l, r)
15    let res = 0
16    for (l += this.n, r += this.n; l < r; l >>= 1, r >>= 1) {
17      if (l & 1) res += this.sum[l++]!
18      if (r & 1) res += this.sum[--r]!
19    }
20    return res
21  }
22 
23  update(i: number, value: number): void {
24    let pos = i + this.n
25    this.sum[pos] = value
26    for (pos >>= 1; pos > 0; pos >>= 1) {
27      this.sum[pos] = this.sum[2 * pos]! + this.sum[2 * pos + 1]!
28    }
29  }
30}