Segment Trees & Fenwick Trees

Array:  [2, 4, 6, 8, 10]
 
Segment tree (range sum):
        30
       /  \
      12   18
     / \   / \
    2   10  14  4
       / \   / \
       4   6  8  6

class BIT {
  constructor(n) { this.tree = Array(n + 1).fill(0); }
 
  update(i, delta) {
    for (; i < this.tree.length; i += i & (-i))
      this.tree[i] += delta;
  }
 
  query(i) {  // prefix sum [1..i]
    let sum = 0;
    for (; i > 0; i -= i & (-i))
      sum += this.tree[i];
    return sum;
  }
 
  rangeQuery(l, r) { return this.query(r) - this.query(l - 1); }
}