SegmentTree

#Purpose

For operators and arrays satisfying commutativity and associativity and having an identity element, it quickly computes the operation result of a continuous sub-range.
例: Addition of real numbers forms an Abelian group, so it satisfies the above properties. Specifically:

• Commutativity: $a + b = b + a$
• Associativity: $(a+b)+c = a+(b+c)$
• Existence of identity element: $a + 0 = a$

Since it satisfies these, it can be loaded onto a Segment Tree to quickly compute the sum of continuous sub-ranges.
Similar data structure: LazySegmentTree

#Time Complexity

Initialization: $O(n)$ Query: $\log(n)$

#Usage

#Declaration

1
SegmentTree<class> seg(array_length, lambda_for_binary_operation, identity_element);

#Initialization

1
seg.set(i,x);

assigns x to the i-th element.
After array construction,

1
seg.build();

builds the segment tree.

#Update

After construction,

1
seg.update(i,x)

updates the i-th element to x and rebuilds.

#Query

1
seg.query(a,b)

returns the evaluated binary operation over the half-open interval $\left[ a,b \right)$.

#Implementation

1
template <class T>
2
class SegmentTree {
3
public:
4
  int n;
5
  vector<T> s;
6
  const function<T(T, T)> f;
7
  const T m;
8
  SegmentTree(int _n, const function<T(T, T)> &_f, const T &_m) : f(_f), m(_m) {
9
    n = 1;
10
    while (n < _n)
11
      n <<= 1;
12
    s.assign(2 * n, _m);
13
  }
14
  void set(int k, const T &x) {
15
    s[k + n] = x;
16
  }
17
  void build() {
18
    for (int k = n - 1; k > 0; k--)
19
      s[k] = f(s[2 * k + 0], s[2 * k + 1]);
20
  }
21
  void update(int k, const T &x) {
22
    k += n;
23
    s[k] = x;
24
    while (k >>= 1)
25
      s[k] = f(s[2 * k + 0], s[2 * k + 1]);
26
  }
27
  T query(int a, int b) {
28
    T L = m, R = m;
29
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
30
      if (a & 1)
31
        L = f(L, s[a++]);
32
      if (b & 1)
33
        R = f(s[--b], R);
34
    }
35
    return f(L, R);
36
  }
37
  T operator[](const int &k) const {
38
    return s[k + n];
39
  }
40
};

#Verify

//TODO

#Example

To quickly compute the sum of a continuous interval:

1
SegmentTree<int> seg(n, [](int a, int b){ return a+b; }, 0);
2

you just need to provide a lambda like this.