segment-tree.js

function SegmentTree(size, merge, zero) {
  const tree = [];
  return {
    tree,
    update(index, value) {
      update(0, 0, size - 1, index, value)
    },
    query(l, r) {
      return query(0, 0, size - 1, l, r)
    },
    build(values) {
      build(0, 0, size - 1, values);
    }
  };

  function query(v, tl, tr, l, r) {
    if (l === tl && r === tr) {
      return tree[v] || zero;
    }
    const tm = Math.floor((tl + tr) / 2);
    if (r <= tm) {
      return query(v * 2 + 1, tl, tm, l, r)
    } else if (l >= tm + 1) {
      return query(v * 2 + 2, tm + 1, tr, l, r);
    } else {
      const lq = query(v * 2 + 1, tl, tm, l, tm);
      const rq = query(v * 2 + 2, tm + 1, tr, tm + 1, r);
      return merge(lq, rq);
    }
  }

  function update(v, tl, tr, index, value) {
    if (tl === tr) {
      return tree[v] = value;
    } else {
      const tm = Math.floor((tl + tr) / 2);
      let vl, vr;
      if (index <= tm) {
        vl = update(v * 2 + 1, tl, tm, index, value);
        vr = tree[v * 2 + 2] || zero;
      } else {
        vl = tree[v * 2 + 1] || zero;
        vr = update(v * 2 + 2, tm + 1, tr, index, value);
      }
      return tree[v] = merge(vl, vr);
    }
  }

  function build(v, tl, tr, values) {
    if (tl === tr) {
      return tree[v] = values[tl];
    } else {
      const tm = Math.floor((tl + tr) / 2);
      const vl = build(v * 2 + 1, tl, tm, values);
      const vr = build(v * 2 + 2, tm + 1, tr, values);
      return tree[v] = merge(vl, vr);
    }
  }
}