segment-tree/lazy-segment-tree.hpp

• View this file on GitHub
• Last update: 2021-07-11 08:39:39+09:00
• Include: #include "segment-tree/lazy-segment-tree.hpp"

Verified with

• verify/verify-unit-test/lazyseg-setval-2.test.cpp
• verify/verify-unit-test/rbst-segment-tree.test.cpp
• verify/verify-yosupo-ds/yosupo-lazysegtree.test.cpp
• verify/verify-yosupo-ds/yosupo-range-affine-point-get.test.cpp

Code

#pragma once

// LazySegmentTree
template <typename T, typename E, typename F, typename G, typename H>
struct LazySegmentTree {
  int n, height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  LazySegmentTree(int _n, F _f, G _g, H _h, T _ti, E _ei)
      : f(_f), g(_g), h(_h), ti(_ti), ei(_ei) {
    init(_n);
  }
  LazySegmentTree(const vector<T> &v, F _f, G _g, H _h, T _ti, E _ei)
      : f(_f), g(_g), h(_h), ti(_ti), ei(_ei) {
    init((int)v.size());
    build(v);
  }
  void init(int _n) {
    n = 1;
    height = 0;
    while (n < _n) n <<= 1, height++;
    dat.assign(2 * n, ti);
    laz.assign(2 * n, ei);
  }
  void build(const vector<T> &v) {
    int _n = v.size();
    init(_n);
    for (int i = 0; i < _n; i++) dat[n + i] = v[i];
    for (int i = n - 1; i; i--)
      dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
  }
  inline T reflect(int k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); }
  inline void eval(int k) {
    if (laz[k] == ei) return;
    laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]);
    laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]);
    dat[k] = reflect(k);
    laz[k] = ei;
  }
  inline void thrust(int k) {
    for (int i = height; i; i--) eval(k >> i);
  }
  inline void recalc(int k) {
    while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1));
  }
  void update(int a, int b, E x) {
    if (a >= b) return;
    thrust(a += n);
    thrust(b += n - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) laz[l] = h(laz[l], x), l++;
      if (r & 1) --r, laz[r] = h(laz[r], x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a, T x) {
    thrust(a += n);
    dat[a] = x;
    laz[a] = ei;
    recalc(a);
  }
  T get_val(int a) {
    thrust(a += n);
    return reflect(a);
  }
  T query(int a, int b) {
    if (a >= b) return ti;
    thrust(a += n);
    thrust(b += n - 1);
    T vl = ti, vr = ti;
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, reflect(l++));
      if (r & 1) vr = f(reflect(--r), vr);
    }
    return f(vl, vr);
  }
};

#line 2 "segment-tree/lazy-segment-tree.hpp"

// LazySegmentTree
template <typename T, typename E, typename F, typename G, typename H>
struct LazySegmentTree {
  int n, height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  LazySegmentTree(int _n, F _f, G _g, H _h, T _ti, E _ei)
      : f(_f), g(_g), h(_h), ti(_ti), ei(_ei) {
    init(_n);
  }
  LazySegmentTree(const vector<T> &v, F _f, G _g, H _h, T _ti, E _ei)
      : f(_f), g(_g), h(_h), ti(_ti), ei(_ei) {
    init((int)v.size());
    build(v);
  }
  void init(int _n) {
    n = 1;
    height = 0;
    while (n < _n) n <<= 1, height++;
    dat.assign(2 * n, ti);
    laz.assign(2 * n, ei);
  }
  void build(const vector<T> &v) {
    int _n = v.size();
    init(_n);
    for (int i = 0; i < _n; i++) dat[n + i] = v[i];
    for (int i = n - 1; i; i--)
      dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
  }
  inline T reflect(int k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); }
  inline void eval(int k) {
    if (laz[k] == ei) return;
    laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]);
    laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]);
    dat[k] = reflect(k);
    laz[k] = ei;
  }
  inline void thrust(int k) {
    for (int i = height; i; i--) eval(k >> i);
  }
  inline void recalc(int k) {
    while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1));
  }
  void update(int a, int b, E x) {
    if (a >= b) return;
    thrust(a += n);
    thrust(b += n - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) laz[l] = h(laz[l], x), l++;
      if (r & 1) --r, laz[r] = h(laz[r], x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a, T x) {
    thrust(a += n);
    dat[a] = x;
    laz[a] = ei;
    recalc(a);
  }
  T get_val(int a) {
    thrust(a += n);
    return reflect(a);
  }
  T query(int a, int b) {
    if (a >= b) return ti;
    thrust(a += n);
    thrust(b += n - 1);
    T vl = ti, vr = ti;
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, reflect(l++));
      if (r & 1) vr = f(reflect(--r), vr);
    }
    return f(vl, vr);
  }
};

Back to top page