Sparse Segment Tree (for IOI 2013 Game)

SparseSegmentTree.hpp

template <class ValueTy> struct Tree {
  int L, R;
  Tree *lc, *rc;
  ValueTy Val;
  Tree() = default;
  Tree(int L, int R) : L(L), R(R), lc(nullptr), rc(nullptr), Val() {}
  void pull() {
    Val = 0;
    if (lc)
      Val += lc->Val;
    if (rc)
      Val += rc->Val;
  }
  static void ensure(Tree *&T, int p, int L, int R) {
    if (!T) {
      T = new Tree(p, p + 1);
      return;
    }
    if (T->L <= p && p < T->R) {
      return;
    }
    auto mid = [&L, &R]() { return (L + R) / 2; };
    while ((p < mid()) == (T->L < mid()))
      ((p < mid()) ? R : L) = mid();
    Tree *T_new = new Tree(L, R);
    ((T->L < mid()) ? T_new->lc : T_new->rc) = T;
    T = T_new;
    T->pull();
  }
  void update(int p, const ValueTy &Val_new) {
    if (L + 1 == R) {
      Val = Val_new;
    } else {
      int mid = (L + R) / 2;
      if (p < mid) {
        ensure(lc, p, L, mid);
        lc->update(p, Val_new);
      } else {
        ensure(rc, p, mid, R);
        rc->update(p, Val_new);
      }
      pull();
    }
  }
  ValueTy query(int qL, int qR) {
    if (qR <= L || R <= qL)
      return ValueTy();
    if (qL <= L && R <= qR)
      return Val;
    auto ans = ValueTy();
    if (lc)
      ans = ans + lc->query(qL, qR);
    if (rc)
      ans = ans + rc->query(qL, qR);
    return ans;
  }
  const ValueTy &operator=(const ValueTy &Other) {
    L = Other.L;
    R = Other.R;
    Val = Other.Val;
    if (Other.lc) {
      lc = new Tree();
      *lc = *Other.lc;
    }
    if (Other.rc) {
      rc = new Tree();
      *rc = *Other.rc;
    }
    return *this;
  }
};

SparseSegmentTree2.hpp

template <class ValueTy> struct Tree {
  int L, R;
  Tree *lc, *rc;
  ValueTy Val;
  Tree() = default;
  Tree(int L, int R) : L(L), R(R), lc(nullptr), rc(nullptr), Val() {}
  void pull() {
    Val = 0;
    if (lc)
      Val += lc->Val;
    if (rc)
      Val += rc->Val;
  }
  static void ensure(Tree *&T, int p, int L, int R) {
    if (!T) {
      T = new Tree(p, p);
      return;
    }
    if (T->L <= p && p <= T->R) {
      return;
    }
    bool is_update = false;
    do {
      is_update = false;
      int mid = (L + R) / 2;
      if (p <= mid && T->R <= mid) {
        R = mid;
        is_update = true;
      }
      if (p > mid && T->L > mid) {
        L = mid + 1;
        is_update = true;
      }
    } while (is_update);
    Tree *T_new = new Tree(L, R);
    ((T->L <= (L + R) / 2) ? T_new->lc : T_new->rc) = T;
    T = T_new;
    T->pull();
  }
  void update(int p, const ValueTy &Val_new) {
    if (L == R) {
      Val = Val_new;
    } else {
      int mid = (L + R) / 2;
      if (p <= mid) {
        ensure(lc, p, L, mid);
        lc->update(p, Val_new);
      } else {
        ensure(rc, p, mid + 1, R);
        rc->update(p, Val_new);
      }
      pull();
    }
  }
  ValueTy query(int qL, int qR) {
    if (qR < L || R < qL)
      return ValueTy();
    if (qL <= L && R <= qR)
      return Val;
    auto ans = ValueTy();
    if (lc)
      ans = ans + lc->query(qL, qR);
    if (rc)
      ans = ans + rc->query(qL, qR);
    return ans;
  }
  const ValueTy &operator=(const ValueTy &Other) {
    L = Other.L;
    R = Other.R;
    Val = Other.Val;
    if (Other.lc) {
      lc = new Tree();
      *lc = *Other.lc;
    }
    if (Other.rc) {
      rc = new Tree();
      *rc = *Other.rc;
    }
    return *this;
  }
};