資料結構

1class SegmentTree {
2  private tree: number[];
3 
4  constructor(private a: number[]) {
5    this.tree = new Array(4 * Math.max(1, a.length)).fill(0);
6    if (a.length) this.build(1, 0, a.length - 1);
7  }
8 
9  private build(node: number, lo: number, hi: number): void {
10    if (lo === hi) { this.tree[node] = this.a[lo]; return; }
11    const mid = (lo + hi) >> 1;
12    this.build(2 * node, lo, mid);
13    this.build(2 * node + 1, mid + 1, hi);
14    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
15  }
16 
17  update(i: number, value: number, node = 1, lo = 0, hi = this.a.length - 1): void {
18    if (lo === hi) { this.a[i] = value; this.tree[node] = value; return; }
19    const mid = (lo + hi) >> 1;
20    if (i <= mid) this.update(i, value, 2 * node, lo, mid);
21    else this.update(i, value, 2 * node + 1, mid + 1, hi);
22    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
23  }
24 
25  query(l: number, r: number, node = 1, lo = 0, hi = this.a.length - 1): number {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return this.tree[node];
28    const mid = (lo + hi) >> 1;
29    return this.query(l, r, 2 * node, lo, mid)
30      + this.query(l, r, 2 * node + 1, mid + 1, hi);
31  }
32}
33 
34class FenwickTree {
35  private t: number[];
36 
37  constructor(n: number) {
38    this.t = new Array(n + 1).fill(0);
39  }
40 
41  // Add delta at 0-based index i: climb by the lowest set bit.
42  add(i: number, delta: number): void {
43    for (let j = i + 1; j < this.t.length; j += j & -j) this.t[j] += delta;
44  }
45 
46  // Sum of the first count elements: descend by the lowest set bit.
47  prefix(count: number): number {
48    let sum = 0;
49    for (let j = count; j > 0; j -= j & -j) sum += this.t[j];
50    return sum;
51  }
52 
53  rangeSum(l: number, r: number): number {
54    return this.prefix(r + 1) - this.prefix(l);
55  }
56}