Cacher is the code snippet organizer for pro developers

template <typename T>
struct SegmentTree {
  using Operator = function<T(T, T)>;

  vector<T> data;
  Operator op;
  T e;  // Identity element. op(x, e) = op(e, x) = x.
  int size = 1;

  SegmentTree(int n, Operator o, T e) : op(o), e(e) {
    while (size < n) size *= 2;
    data.resize(2 * size - 1, e);
  }

  SegmentTree(const vector<T>& v, Operator o, T e)
      : SegmentTree(v.size(), o, e) {
    int n = v.size();
    for (int i = 0; i < n; ++i) {
      data[i + size - 1] = v[i];
    }
    for (int i = size - 2; i >= 0; --i) {
      data[i] = op(data[2 * i + 1], data[2 * i + 2]);
    }
  }
  
  T Get(int k) { return data[k + size - 1]; }

  void Update(int k, T x) {
    k += size - 1;
    data[k] = x;

    while (k > 0) {
      k = (k - 1) / 2;
      data[k] = op(data[2 * k + 1], data[2 * k + 2]);
    }
  }

  // Return value in [a, b]
  T Query(int a, int b) { return Query(a, b + 1, 0, 0, size); }
  // Return value in [a, b) with target node index k and range [l, r).
  T Query(int a, int b, int k, int l, int r) {
    // [l, r) is out of the query bound.
    if (l >= b || r <= a) {
      return e;
    }

    // [l, r) is completely within the query range.
    if (l >= a && r <= b) {
      return data[k];
    }

    T left = Query(a, b, 2 * k + 1, l, (l + r) / 2);
    T right = Query(a, b, 2 * k + 2, (l + r) / 2, r);
    return op(left, right);
  }

  void Print() {
    int k = 1;
    for (int i = 0; i < (int)data.size(); ++i) {
      if (i == k) {
        k = 2 * k + 1;
        cout << "| ";
      }
      if (data[i] != e) {
        cout << data[i] << " ";
      } else {
        cout << "X ";
      }
    }
    cout << endl;
  }
};

• Range Minimum Query Tree
  • op = [](T left, T right) { return min(left, right); }
  • e = 1e9
• Range Sum Query Tree
  • op = [](T left, T right) { return left + right; }
  • e = 0

template<typename T>
struct SegmentTree {  // For Range Minimum Query
  const T kInvalid;
  vector<T> data;
  int size = -1;

  SegmentTree(int N, int v = INT_MAX) : kInvalid(v) {
    size = 1;
    while (size < N) size *= 2;
    data.resize(2 * size - 1, kInvalid);
  }

  void Update(int k, T x) {
    k += size - 1;
    data[k] = x;

    while(k > 0) {
      k = (k - 1) / 2;
      data[k] = min(data[2 * k + 1], data[2 * k + 2]);
    }
  }

  // return value in [a, b]
  T Query(int a, int b) const { return Query(a, b + 1, 0, 0, size); }
  // return value in [a, b) by searching index k node which cover [l, r) region.
  T Query(int a, int b, int k, int l, int r) const {
    // l/r is out of bound.
    if (r <= a || b <= l) {
      return kInvalid;
    }

    // cover full range.
    if (a <= l && r <= b) {
      return data[k];
    }

    T left  = Query(a, b, 2 * k + 1, l, (l + r) /2);
    T right = Query(a, b, 2 * k + 2, (l + r) /2, r);
    return min(left, right);
  }

  void Print() {
    int k = 1;
    for (int i = 0; i < data.size(); ++i) {
      if (i == k) {
        k = 2 * k + 1; cout << "| ";
      }
      cout << data[i] << " ";
    }
    cout << endl;
  }
};

template<typename T>
struct SegmentTree {  // For Range Maximum Query
  const T kInvalid;
  vector<T> data;
  int size = -1;

  SegmentTree(int N, int v = INT_MIN) : kInvalid(v) {
    size = 1;
    while (size < N) size *= 2;
    data.resize(2 * size - 1, kInvalid);
  }

  void Update(int k, T x) {
    k += size - 1;
    data[k] = x;

    while(k > 0) {
      k = (k - 1) / 2;
      data[k] = max(data[2 * k + 1], data[2 * k + 2]);
    }
  }

  // return value in [a, b]
  T Query(int a, int b) const { return Query(a, b + 1, 0, 0, size); }
  // return value in [a, b) by searching index k node which cover [l, r) region.
  T Query(int a, int b, int k, int l, int r) const {
    // l/r is out of bound.
    if (r <= a || b <= l) {
      return kInvalid;
    }

    // cover full range.
    if (a <= l && r <= b) {
      return data[k];
    }

    T left  = Query(a, b, 2 * k + 1, l, (l + r) /2);
    T right = Query(a, b, 2 * k + 2, (l + r) /2, r);
    return max(left, right);
  }

  void Print() {
    int k = 1;
    for (int i = 0; i < data.size(); ++i) {
      if (i == k) {
        k = 2 * k + 1; cout << "| ";
      }
      cout << data[i] << " ";
    }
    cout << endl;
  }
};

template<typename T>
struct SegmentTree {  // For Range Sum Query
  vector<T> data;
  int size = -1;

  SegmentTree(int N) {
    size = 1;
    while (size < N) size *= 2;
    data.resize(2 * size - 1, 0);
  }

  void Add(int k, T x) {
    k += size - 1;
    data[k] += x;

    while(k > 0) {
      k = (k - 1) / 2;
      data[k] = data[2 * k + 1] + data[2 * k + 2];
    }
  }

  // return value in [a, b]
  T Query(int a, int b) const { return Query(a, b + 1, 0, 0, size); }
  // return value in [a, b)
  // by searching index k node which cover [l, r) region.
  T Query(int a, int b, int k, int l, int r) const {
    // l/r is out of bound.
    if (r <= a || b <= l) return 0;

    // cover full range.
    if (a <= l && r <= b) return data[k];

    T left  = Query(a, b, 2 * k + 1, l, (l + r) /2);
    T right = Query(a, b, 2 * k + 2, (l + r) /2, r);
    return left + right;
  }

  void Print() {
    int k = 1;
    for (int i = 0; i < data.size(); ++i) {
      if (i == k) {
        k = 2 * k + 1; cout << "| ";
      }
      cout << data[i] << " ";
    }
    cout << endl;
  }
};