Segment Tree Simple

segment_tree.cpp

template<type T>
void build(T[] tree, T[] vals, size_t n) {
  if (n == 0) {
    return;
  }
  for (auto i = n; i < 2 * n; ++i) {
    tree[i] = vals[i];
  }
  for (auto i = n - 1; i > 0; --i) {
    tree[i] = tree[i * 2] + tree[i * 2 + 1];
  }
}


template<type T>
void update(T[] tree, size_t pos, T val, size_t n) {
  pos += n;
  tree[pos] = val;
  while (pos > 1) {
    pos = pos / 2;
    tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
  }
}


template<type T>
T query(T[] tree, size_t l, size_t r, size_t n) {
  l += n;
  r += n;
  T sum = 0;
  while (l <= r) {
    if ((l % 2) == 1) {  // right sibling
      sum += tree[l];
      ++l;  // move range
    }
    if ((r % 2) == 0) {  // left sibling
      sum += tree[r];
      --r;  // move range
    }
    l /= 2;  // move up
    r /= 2;  // move up
  }
  return sum;
}