{ array: number[], queryRange: [number, number] }
1BUILD: fill tree so each node = sum of its range2function build(node, start, end):3 if start == end: # leaf: single element4 tree[node] = arr[start]5 return6 mid = (start + end) / 2 # split range7 build(2*node, start, mid)8 build(2*node+1, mid+1, end)9 tree[node] = tree[2*node] + tree[2*node+1]1011QUERY: get sum of array [l..r]12function query(node, start, end, l, r):13 if l <= start and end <= r: # node inside query14 return tree[node]15 if end < l or start > r: # no overlap16 return 017 mid = (start + end) / 218 return query(left,l,r) + query(right,l,r)
1class SegmentTree {2 private tree: number[];3 constructor(private arr: number[]) {4 this.tree = new Array(4 * arr.length).fill(0);5 this.build(1, 0, arr.length - 1);6 }78 private build(node: number, start: number, end: number) {9 if (start === end) { this.tree[node] = this.arr[start]; return; }10 const mid = (start + end) >> 1;11 this.build(2 * node, start, mid);12 this.build(2 * node + 1, mid + 1, end);13 this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];14 }1516 query(node: number, start: number, end: number, l: number, r: number): number {17 if (l <= start && end <= r) return this.tree[node];18 if (end < l || start > r) return 0;19 const mid = (start + end) >> 1;20 return this.query(2*node, start, mid, l, r)21 + this.query(2*node+1, mid+1, end, l, r);22 }23}