Lazy-Segment-Tree(遅延伝搬セグメント木) (structure/segment-tree/lazy-segment-tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "structure/segment-tree/lazy-segment-tree.hpp"

概要

遅延伝搬を用いることで, 区間に対する更新が可能になる. コンストラクタに対し追加で作用素モノイドの情報も与える.

使い方

計算量のオーダーを表記していない関数は全て $O(\log n)$ で動作する.

• LazySegmentTree(n, f, g, h, M1, OM0): サイズ n で初期化する. ここで f は2つの区間の要素をマージする二項演算, g は要素と作用素をマージする二項演算, h は作用素同士をマージする二項演算, M1 はモノイドの単位元, OM0 は作用素の単位元である. $O(n)$
• LazySegmentTree(v, f, g, h, M1, OM0): 配列 v で初期化する. 第2引数以降は上と同様. $O(n)$
• build(v): 配列 v で初期化する. $O(n)$
• set(k, x): k 番目の要素を x に更新する.
• get(k): k 番目の要素を返す.
• operator[k]: k 番目の要素を返す.
• prod(l, r): 区間 $[l, r)$ に対して二項演算した結果を返す.
• all_prod(): 全体を二項演算した結果を返す. $O(1)$
• apply(k, x): k 番目の要素に作用素 x を適用する.
• apply(l, r, x): 区間 $[l, r)$ に対して作用素 x を適用する.
• find_first(a, check): $[a,x)$ が check を満たす最初の要素位置 $x$ を返す. 存在しないとき $n$ を返す.
• find_last(b, check): $[x,b)$ が check を満たす最後の要素位置 $x$ を返す. 存在しないとき $-1$ を返す.

auto seg = get_lazy_segment_tree(N, f, g, h, M1, OM0); のようにすると decltype(f) などを用いなくてすむ.

Required by

• Permutation Tree(順列木) (structure/others/permutation-tree.hpp)

Verified with

• test/verify/aoj-2450.test.cpp
• test/verify/yosupo-range-affine-range-sum.test.cpp
• test/verify/yukicoder-1720.test.cpp

Code

/**
 * @brief Lazy-Segment-Tree(遅延伝搬セグメント木)
 * 
 */
template< typename T, typename E, typename F, typename G, typename H >
struct LazySegmentTree {
private:
  int n{}, sz{}, height{};
  vector< T > data;
  vector< E > lazy;
  const F f;
  const G g;
  const H h;
  const T ti;
  const E ei;

  inline void update(int k) {
    data[k] = f(data[2 * k + 0], data[2 * k + 1]);
  }

  inline void all_apply(int k, const E &x) {
    data[k] = g(data[k], x);
    if(k < sz) lazy[k] = h(lazy[k], x);
  }

  inline void propagate(int k) {
    if(lazy[k] != ei) {
      all_apply(2 * k + 0, lazy[k]);
      all_apply(2 * k + 1, lazy[k]);
      lazy[k] = ei;
    }
  }

public:
  LazySegmentTree() = default;

  explicit LazySegmentTree(int n, const F f, const G g, const H h,
                           const T &ti, const E &ei)
      : n(n), f(f), g(g), h(h), ti(ti), ei(ei) {
    sz = 1;
    height = 0;
    while(sz < n) sz <<= 1, height++;
    data.assign(2 * sz, ti);
    lazy.assign(2 * sz, ei);
  }

  explicit LazySegmentTree(const vector< T > &v, const F f, const G g, const H h,
                           const T &ti, const E &ei)
      : LazySegmentTree(v.size(), f, g, h, ti, ei) {
    build(v);
  }

  void build(const vector< T > &v) {
    assert(n == (int) v.size());
    for(int k = 0; k < n; k++) data[k + sz] = v[k];
    for(int k = sz - 1; k > 0; k--) update(k);
  }

  void set(int k, const T &x) {
    k += sz;
    for(int i = height; i > 0; i--) propagate(k >> i);
    data[k] = x;
    for(int i = 1; i <= height; i++) update(k >> i);
  }

  T get(int k) {
    k += sz;
    for(int i = height; i > 0; i--) propagate(k >> i);
    return data[k];
  }

  T operator[](int k) {
    return get(k);
  }

  T prod(int l, int r) {
    if(l >= r) return ti;
    l += sz;
    r += sz;
    for(int i = height; i > 0; i--) {
      if(((l >> i) << i) != l) propagate(l >> i);
      if(((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    T L = ti, R = ti;
    for(; l < r; l >>= 1, r >>= 1) {
      if(l & 1) L = f(L, data[l++]);
      if(r & 1) R = f(data[--r], R);
    }
    return f(L, R);
  }

  T all_prod() const {
    return data[1];
  }

  void apply(int k, const E &x) {
    k += sz;
    for(int i = height; i > 0; i--) propagate(k >> i);
    data[k] = g(data[k], x);
    for(int i = 1; i <= height; i++) update(k >> i);
  }

  void apply(int l, int r, const E &x) {
    if(l >= r) return;
    l += sz;
    r += sz;
    for(int i = height; i > 0; i--) {
      if(((l >> i) << i) != l) propagate(l >> i);
      if(((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      for(; l < r; l >>= 1, r >>= 1) {
        if(l & 1) all_apply(l++, x);
        if(r & 1) all_apply(--r, x);
      }
      l = l2, r = r2;
    }
    for(int i = 1; i <= height; i++) {
      if(((l >> i) << i) != l) update(l >> i);
      if(((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template< typename C >
  int find_first(int l, const C &check) {
    if(l >= n) return n;
    l += sz;
    for(int i = height; i > 0; i--) propagate(l >> i);
    T sum = ti;
    do {
      while((l & 1) == 0) l >>= 1;
      if(check(f(sum, data[l]))) {
        while(l < sz) {
          propagate(l);
          l <<= 1;
          auto nxt = f(sum, data[l]);
          if(not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = f(sum, data[l++]);
    } while((l & -l) != l);
    return n;
  }

  template< typename C >
  int find_last(int r, const C &check) {
    if(r <= 0) return -1;
    r += sz;
    for(int i = height; i > 0; i--) propagate((r - 1) >> i);
    T sum = ti;
    do {
      r--;
      while(r > 1 and (r & 1)) r >>= 1;
      if(check(f(data[r], sum))) {
        while(r < sz) {
          propagate(r);
          r = (r << 1) + 1;
          auto nxt = f(data[r], sum);
          if(not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = f(data[r], sum);
    } while((r & -r) != r);
    return -1;
  }
};

template< typename T, typename E, typename F, typename G, typename H >
LazySegmentTree< T, E, F, G, H > get_lazy_segment_tree
    (int N, const F &f, const G &g, const H &h, const T &ti, const E &ei) {
  return LazySegmentTree{N, f, g, h, ti, ei};
}

template< typename T, typename E, typename F, typename G, typename H >
LazySegmentTree< T, E, F, G, H > get_lazy_segment_tree
    (const vector< T > &v, const F &f, const G &g, const H &h, const T &ti, const E &ei) {
  return LazySegmentTree{v, f, g, h, ti, ei};
}

#line 1 "structure/segment-tree/lazy-segment-tree.hpp"
/**
 * @brief Lazy-Segment-Tree(遅延伝搬セグメント木)
 * 
 */
template< typename T, typename E, typename F, typename G, typename H >
struct LazySegmentTree {
private:
  int n{}, sz{}, height{};
  vector< T > data;
  vector< E > lazy;
  const F f;
  const G g;
  const H h;
  const T ti;
  const E ei;

  inline void update(int k) {
    data[k] = f(data[2 * k + 0], data[2 * k + 1]);
  }

  inline void all_apply(int k, const E &x) {
    data[k] = g(data[k], x);
    if(k < sz) lazy[k] = h(lazy[k], x);
  }

  inline void propagate(int k) {
    if(lazy[k] != ei) {
      all_apply(2 * k + 0, lazy[k]);
      all_apply(2 * k + 1, lazy[k]);
      lazy[k] = ei;
    }
  }

public:
  LazySegmentTree() = default;

  explicit LazySegmentTree(int n, const F f, const G g, const H h,
                           const T &ti, const E &ei)
      : n(n), f(f), g(g), h(h), ti(ti), ei(ei) {
    sz = 1;
    height = 0;
    while(sz < n) sz <<= 1, height++;
    data.assign(2 * sz, ti);
    lazy.assign(2 * sz, ei);
  }

  explicit LazySegmentTree(const vector< T > &v, const F f, const G g, const H h,
                           const T &ti, const E &ei)
      : LazySegmentTree(v.size(), f, g, h, ti, ei) {
    build(v);
  }

  void build(const vector< T > &v) {
    assert(n == (int) v.size());
    for(int k = 0; k < n; k++) data[k + sz] = v[k];
    for(int k = sz - 1; k > 0; k--) update(k);
  }

  void set(int k, const T &x) {
    k += sz;
    for(int i = height; i > 0; i--) propagate(k >> i);
    data[k] = x;
    for(int i = 1; i <= height; i++) update(k >> i);
  }

  T get(int k) {
    k += sz;
    for(int i = height; i > 0; i--) propagate(k >> i);
    return data[k];
  }

  T operator[](int k) {
    return get(k);
  }

  T prod(int l, int r) {
    if(l >= r) return ti;
    l += sz;
    r += sz;
    for(int i = height; i > 0; i--) {
      if(((l >> i) << i) != l) propagate(l >> i);
      if(((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    T L = ti, R = ti;
    for(; l < r; l >>= 1, r >>= 1) {
      if(l & 1) L = f(L, data[l++]);
      if(r & 1) R = f(data[--r], R);
    }
    return f(L, R);
  }

  T all_prod() const {
    return data[1];
  }

  void apply(int k, const E &x) {
    k += sz;
    for(int i = height; i > 0; i--) propagate(k >> i);
    data[k] = g(data[k], x);
    for(int i = 1; i <= height; i++) update(k >> i);
  }

  void apply(int l, int r, const E &x) {
    if(l >= r) return;
    l += sz;
    r += sz;
    for(int i = height; i > 0; i--) {
      if(((l >> i) << i) != l) propagate(l >> i);
      if(((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      for(; l < r; l >>= 1, r >>= 1) {
        if(l & 1) all_apply(l++, x);
        if(r & 1) all_apply(--r, x);
      }
      l = l2, r = r2;
    }
    for(int i = 1; i <= height; i++) {
      if(((l >> i) << i) != l) update(l >> i);
      if(((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template< typename C >
  int find_first(int l, const C &check) {
    if(l >= n) return n;
    l += sz;
    for(int i = height; i > 0; i--) propagate(l >> i);
    T sum = ti;
    do {
      while((l & 1) == 0) l >>= 1;
      if(check(f(sum, data[l]))) {
        while(l < sz) {
          propagate(l);
          l <<= 1;
          auto nxt = f(sum, data[l]);
          if(not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = f(sum, data[l++]);
    } while((l & -l) != l);
    return n;
  }

  template< typename C >
  int find_last(int r, const C &check) {
    if(r <= 0) return -1;
    r += sz;
    for(int i = height; i > 0; i--) propagate((r - 1) >> i);
    T sum = ti;
    do {
      r--;
      while(r > 1 and (r & 1)) r >>= 1;
      if(check(f(data[r], sum))) {
        while(r < sz) {
          propagate(r);
          r = (r << 1) + 1;
          auto nxt = f(data[r], sum);
          if(not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = f(data[r], sum);
    } while((r & -r) != r);
    return -1;
  }
};

template< typename T, typename E, typename F, typename G, typename H >
LazySegmentTree< T, E, F, G, H > get_lazy_segment_tree
    (int N, const F &f, const G &g, const H &h, const T &ti, const E &ei) {
  return LazySegmentTree{N, f, g, h, ti, ei};
}

template< typename T, typename E, typename F, typename G, typename H >
LazySegmentTree< T, E, F, G, H > get_lazy_segment_tree
    (const vector< T > &v, const F &f, const G &g, const H &h, const T &ti, const E &ei) {
  return LazySegmentTree{v, f, g, h, ti, ei};
}

Back to top page