LazySegmentTree

1
LazySegmentTree<class> lseg(配列長, 二項演算するlambda, 単位元);

1
lseg.update(a, b, x);

1
lseg.query(a,b)

1
template <class T>
2
struct LazySegmentTree {
3
  int n;
4
  vector<T> s, lazy;
5
  const function<T(T, T)> f;
6
  const T m;
7
  LazySegmentTree(int _n, const function<T(T, T)> &_f, const T &_m) : s(_n * 4, m), lazy(_n * 4, m), f(_f), m(_m) {
8
    n = 1;
9
    while (n < _n)
10
      n *= 2;
11
    s.assign(n * 2, m);
12
    lazy.assign(n * 2, m);
13
  }
14
  void eval(int k) {
15
    if (lazy[k] == m)
16
      return;
17
    if (k < n - 1) {
18
      lazy[k * 2 + 1] = lazy[k];
19
      lazy[k * 2 + 2] = lazy[k];
20
    }
21
    s[k] = lazy[k];
22
    lazy[k] = m;
23
  }
24
  void update(int a, int b, T x, int k, int l, int r) {
25
    eval(k);
26
    if (a <= l and r <= b) {
27
      lazy[k] = x;
28
      eval(k);
29
    } else if (a < r and l < b) {
30
      update(a, b, x, k * 2 + 1, l, (l + r) / 2);
31
      update(a, b, x, k * 2 + 2, (l + r) / 2, r);
32
      s[k] = f(s[k * 2 + 1], s[k * 2 + 2]);
33
    }
34
  }
35
  void update(int a, int b, T x) { update(a, b, x, 0, 0, n); }
36
  T query_sub(int a, int b, int k, int l, int r) {
37
    eval(k);
38
    if (r <= a or b <= l) {
39
      return m;
40
    } else if (a <= l and r <= b) {
41
      return s[k];
42
    } else {
43
      T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
44
      T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
45
      return f(vl, vr);
46
    }
47
  }
48
  T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
49
};

1
template <class T>
2
struct LazySegmentTree {
3
  int n;
4
  vector<T> s, lazy;
5
  const function<T(T, T)> f;
6
  const T m;
7
  LazySegmentTree(int _n, const function<T(T, T)> &_f, const T &_m) : s(_n * 4, m), lazy(_n * 4, 0), f(_f), m(_m) {
8
    n = 1;
9
    while (n < _n)
10
      n *= 2;
11
    s.assign(n * 2, m);
12
    lazy.assign(n * 2, 0);
13
  }
14
  void eval(int k, int l, int r) {
15
    if (lazy[k] != 0) {
16
      s[k] += lazy[k] * (r - l);
17
      if (k < n - 1) {
18
        lazy[k * 2 + 1] += lazy[k];
19
        lazy[k * 2 + 2] += lazy[k];
20
      }
21
      lazy[k] = 0;
22
    }
23
  }
24
  void update(int a, int b, T x, int k, int l, int r) {
25
    eval(k, l, r);
26
    if (a <= l and r <= b) {
27
      lazy[k] += x;
28
      eval(k, l, r);
29
    } else if (a < r and l < b) {
30
      update(a, b, x, k * 2 + 1, l, (l + r) / 2);
31
      update(a, b, x, k * 2 + 2, (l + r) / 2, r);
32
      s[k] = f(s[k * 2 + 1], s[k * 2 + 2]);
33
    }
34
  }
35
  void update(int a, int b, T x) {
36
    update(a, b, x, 0, 0, n);
37
  }
38
  T query_sub(int a, int b, int k, int l, int r) {
39
    eval(k, l, r);
40
    if (r <= a or b <= l) {
41
      return m;
42
    } else if (a <= l and r <= b) {
43
      return s[k];
44
    } else {
45
      T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
46
      T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
47
      return f(vl, vr);
48
    }
49
  }
50
  T query(int a, int b) {
51
    return query_sub(a, b, 0, 0, n);
52
  }
53
};

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

3
// ~構築~