使用頻度の高い遅延セグメント木
(segment-tree/lazy-segment-tree-utility.hpp)

• View this file on GitHub
• Last update: 2023-05-26 23:34:57+09:00
• Include: #include "segment-tree/lazy-segment-tree-utility.hpp"

使用頻度の高い遅延セグメント木

使用頻度の高い遅延セグメント木を特殊化してライブラリ化したもの。

使い方

以下の6種類の遅延セグメント木を特殊化している。いずれもクラス名(初期値の入ったvector)で初期化、update(l, r, x)で[l, r)にxを作用、query(l, r)で[l, r)の積を取得できる。

• AddMax_LazySegmentTree : Range Add Query & Range Max Query
• AddMin_LazySegmentTree : Range Min Query & Range Min Query
• AddSum_LazySegmentTree : Range Sum Query & Range Sum Query
• UpdateMax_LazySegmentTree : Range Update Query & Range Max Query
• UpdateMin_LazySegmentTree : Range Update Query & Range Min Query
• UpdateSum_LazySegmentTree : Range Update Query & Range Sum Query

Verified with

• verify/verify-aoj-dsl/aoj-dsl-2-d.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-e.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-f-max.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-f.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-g.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-h-max.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-h.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-i.test.cpp
• verify/verify-aoj-grl/aoj-grl-5-e.test.cpp
• verify/verify-unit-test/lazyseg-bsearch.test.cpp
• verify/verify-unit-test/lazyseg-setval.test.cpp
• verify/verify-yosupo-ds/yosupo-lazysegtree-2.test.cpp
• verify/verify-yosupo-ds/yosupo-range-affine-point-get-2.test.cpp

Code

#pragma once

template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E),
          T (*ti)(), E (*ei)()>
struct LazySegmentTreeBase {
  int n, log, s;
  vector<T> val;
  vector<E> laz;

  explicit LazySegmentTreeBase() {}
  explicit LazySegmentTreeBase(const vector<T>& vc) { init(vc); }

  void init(const vector<T>& vc) {
    n = 1, log = 0, s = vc.size();
    while (n < s) n <<= 1, log++;
    val.resize(2 * n, ti());
    laz.resize(n, ei());
    for (int i = 0; i < s; ++i) val[i + n] = vc[i];
    for (int i = n - 1; i; --i) _update(i);
  }

  void update(int l, int r, const E& x) {
    if (l == r) return;
    l += n, r += n;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) _push(l >> i);
      if (((r >> i) << i) != r) _push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) _apply(l++, x);
        if (r & 1) _apply(--r, x);
        l >>= 1;
        r >>= 1;
      }
      l = l2;
      r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) _update(l >> i);
      if (((r >> i) << i) != r) _update((r - 1) >> i);
    }
  }

  T query(int l, int r) {
    if (l == r) return ti();
    l += n, r += n;
    T L = ti(), R = ti();
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) _push(l >> i);
      if (((r >> i) << i) != r) _push((r - 1) >> i);
    }
    while (l < r) {
      if (l & 1) L = f(L, val[l++]);
      if (r & 1) R = f(val[--r], R);
      l >>= 1;
      r >>= 1;
    }
    return f(L, R);
  }

  void set_val(int k, const T& x) {
    k += n;
    for (int i = log; i >= 1; i--) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _push(k >> i);
    }
    val[k] = x;
    for (int i = 1; i <= log; i++) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _update(k >> i);
    }
  }

  void update_val(int k, const E& x) {
    k += n;
    for (int i = log; i >= 1; i--) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _push(k >> i);
    }
    val[k] = g(val[k], x);
    for (int i = 1; i <= log; i++) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _update(k >> i);
    }
  }

  T get_val(int k) {
    k += n;
    for (int i = log; i >= 1; i--) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _push(k >> i);
    }
    return val[k];
  }

  template <class G>
  int max_right(int l, G check) {
    assert(0 <= l && l <= s);
    assert(check(ei()));
    if (l == n) return n;
    l += n;
    for (int i = log; i >= 1; i--) _push(l >> i);
    T sm = ti();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!check(f(sm, val[l]))) {
        while (l < n) {
          _push(l);
          l = (2 * l);
          if (check(f(sm, val[l]))) {
            sm = f(sm, val[l]);
            l++;
          }
        }
        return l - n;
      }
      sm = f(sm, val[l]);
      l++;
    } while ((l & -l) != l);
    return s;
  }

  template <class G>
  int min_left(int r, G check) {
    assert(0 <= r && r <= s);
    assert(check(ei()));
    if (r == 0) return 0;
    r += n;
    for (int i = log; i >= 1; i--) _push((r - 1) >> i);
    T sm = ti();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(f(val[r], sm))) {
        while (r < n) {
          _push(r);
          r = (2 * r + 1);
          if (check(f(val[r], sm))) {
            sm = f(val[r], sm);
            r--;
          }
        }
        return r + 1 - n;
      }
      sm = f(val[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  void _push(int i) {
    if (laz[i] != ei()) {
      val[2 * i + 0] = g(val[2 * i + 0], laz[i]);
      val[2 * i + 1] = g(val[2 * i + 1], laz[i]);
      if (2 * i < n) {
        compose(laz[2 * i + 0], laz[i]);
        compose(laz[2 * i + 1], laz[i]);
      }
      laz[i] = ei();
    }
  }
  inline void _update(int i) { val[i] = f(val[2 * i + 0], val[2 * i + 1]); }
  inline void _apply(int i, const E& x) {
    if (x != ei()) {
      val[i] = g(val[i], x);
      if (i < n) compose(laz[i], x);
    }
  }
  inline void compose(E& a, const E& b) { a = a == ei() ? b : h(a, b); }
};

namespace SegmentTreeUtil {

template <typename T>
struct Pair {
  T first, second;
  Pair() = default;
  Pair(const T& f, const T& s) : first(f), second(s) {}
  operator T() const { return first; }
  friend ostream& operator<<(ostream& os, const Pair<T>& p) {
    os << T(p.first);
    return os;
  }
};

template <typename T>
T Mx(T a, T b) {
  return max(a, b);
}
template <typename T>
T Mn(T a, T b) {
  return min(a, b);
}
template <typename T>
T Update(T, T b) {
  return b;
}
template <typename T>
T Add(T a, T b) {
  return a + b;
}
template <typename T>
Pair<T> Psum(Pair<T> a, Pair<T> b) {
  return Pair<T>(a.first + b.first, a.second + b.second);
}
template <typename T>
Pair<T> Padd(Pair<T> a, T b) {
  return Pair<T>(a.first + a.second * b, a.second);
}
template <typename T>
Pair<T> PUpdate(Pair<T> a, T b) {
  return Pair<T>(a.second * b, a.second);
}
template <typename T>
Pair<T> Pid() {
  return Pair<T>(0, 0);
}
template <typename T>
T Zero() {
  return T(0);
}
template <typename T, T val>
T Const() {
  return val;
}

template <typename T, T MINF>
struct AddMax_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mx<T>, Add<T>, Add<T>, Const<T, MINF>, Zero<T>> {
  using base =
      LazySegmentTreeBase<T, T, Mx<T>, Add<T>, Add<T>, Const<T, MINF>, Zero<T>>;
  AddMax_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T, T INF>
struct AddMin_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mn<T>, Add<T>, Add<T>, Const<T, INF>, Zero<T>> {
  using base =
      LazySegmentTreeBase<T, T, Mn<T>, Add<T>, Add<T>, Const<T, INF>, Zero<T>>;
  AddMin_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T>
struct AddSum_LazySegmentTree
    : LazySegmentTreeBase<Pair<T>, T, Psum<T>, Padd<T>, Add<T>, Pid<T>, Zero<T>> {
  using base =
      LazySegmentTreeBase<Pair<T>, T, Psum<T>, Padd<T>, Add<T>, Pid<T>, Zero<T>>;
  AddSum_LazySegmentTree(const vector<T>& v) {
    vector<Pair<T>> w(v.size());
    for (int i = 0; i < (int)v.size(); i++) w[i] = Pair<T>(v[i], 1);
    base::init(w);
  }
};

template <typename T, T MINF>
struct UpdateMax_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mx<T>, Update<T>, Update<T>, Const<T, MINF>,
                      Const<T, MINF>> {
  using base = LazySegmentTreeBase<T, T, Mx<T>, Update<T>, Update<T>,
                               Const<T, MINF>, Const<T, MINF>>;
  UpdateMax_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T, T INF>
struct UpdateMin_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mn<T>, Update<T>, Update<T>, Const<T, INF>,
                      Const<T, INF>> {
  using base = LazySegmentTreeBase<T, T, Mn<T>, Update<T>, Update<T>, Const<T, INF>,
                               Const<T, INF>>;
  UpdateMin_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T, T UNUSED_VALUE>
struct UpdateSum_LazySegmentTree
    : LazySegmentTreeBase<Pair<T>, T, Psum<T>, PUpdate<T>, Update<T>, Pid<T>,
                      Const<T, UNUSED_VALUE>> {
  using base = LazySegmentTreeBase<Pair<T>, T, Psum<T>, PUpdate<T>, Update<T>,
                               Pid<T>, Const<T, UNUSED_VALUE>>;
  UpdateSum_LazySegmentTree(const vector<T>& v) {
    vector<Pair<T>> w(v.size());
    for (int i = 0; i < (int)v.size(); i++) w[i] = Pair<T>(v[i], 1);
    base::init(w);
  }
};

}  // namespace SegmentTreeUtil
using SegmentTreeUtil::AddMax_LazySegmentTree;
using SegmentTreeUtil::AddMin_LazySegmentTree;
using SegmentTreeUtil::AddSum_LazySegmentTree;
using SegmentTreeUtil::UpdateMax_LazySegmentTree;
using SegmentTreeUtil::UpdateMin_LazySegmentTree;
using SegmentTreeUtil::UpdateSum_LazySegmentTree;

/**
 * @brief 使用頻度の高い遅延セグメント木
 * @docs docs/segment-tree/lazy-segment-tree-utility.md
 */

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

template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E),
          T (*ti)(), E (*ei)()>
struct LazySegmentTreeBase {
  int n, log, s;
  vector<T> val;
  vector<E> laz;

  explicit LazySegmentTreeBase() {}
  explicit LazySegmentTreeBase(const vector<T>& vc) { init(vc); }

  void init(const vector<T>& vc) {
    n = 1, log = 0, s = vc.size();
    while (n < s) n <<= 1, log++;
    val.resize(2 * n, ti());
    laz.resize(n, ei());
    for (int i = 0; i < s; ++i) val[i + n] = vc[i];
    for (int i = n - 1; i; --i) _update(i);
  }

  void update(int l, int r, const E& x) {
    if (l == r) return;
    l += n, r += n;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) _push(l >> i);
      if (((r >> i) << i) != r) _push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) _apply(l++, x);
        if (r & 1) _apply(--r, x);
        l >>= 1;
        r >>= 1;
      }
      l = l2;
      r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) _update(l >> i);
      if (((r >> i) << i) != r) _update((r - 1) >> i);
    }
  }

  T query(int l, int r) {
    if (l == r) return ti();
    l += n, r += n;
    T L = ti(), R = ti();
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) _push(l >> i);
      if (((r >> i) << i) != r) _push((r - 1) >> i);
    }
    while (l < r) {
      if (l & 1) L = f(L, val[l++]);
      if (r & 1) R = f(val[--r], R);
      l >>= 1;
      r >>= 1;
    }
    return f(L, R);
  }

  void set_val(int k, const T& x) {
    k += n;
    for (int i = log; i >= 1; i--) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _push(k >> i);
    }
    val[k] = x;
    for (int i = 1; i <= log; i++) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _update(k >> i);
    }
  }

  void update_val(int k, const E& x) {
    k += n;
    for (int i = log; i >= 1; i--) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _push(k >> i);
    }
    val[k] = g(val[k], x);
    for (int i = 1; i <= log; i++) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _update(k >> i);
    }
  }

  T get_val(int k) {
    k += n;
    for (int i = log; i >= 1; i--) {
      if (((k >> i) << i) != k || (((k + 1) >> i) << i) != (k + 1))
        _push(k >> i);
    }
    return val[k];
  }

  template <class G>
  int max_right(int l, G check) {
    assert(0 <= l && l <= s);
    assert(check(ei()));
    if (l == n) return n;
    l += n;
    for (int i = log; i >= 1; i--) _push(l >> i);
    T sm = ti();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!check(f(sm, val[l]))) {
        while (l < n) {
          _push(l);
          l = (2 * l);
          if (check(f(sm, val[l]))) {
            sm = f(sm, val[l]);
            l++;
          }
        }
        return l - n;
      }
      sm = f(sm, val[l]);
      l++;
    } while ((l & -l) != l);
    return s;
  }

  template <class G>
  int min_left(int r, G check) {
    assert(0 <= r && r <= s);
    assert(check(ei()));
    if (r == 0) return 0;
    r += n;
    for (int i = log; i >= 1; i--) _push((r - 1) >> i);
    T sm = ti();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(f(val[r], sm))) {
        while (r < n) {
          _push(r);
          r = (2 * r + 1);
          if (check(f(val[r], sm))) {
            sm = f(val[r], sm);
            r--;
          }
        }
        return r + 1 - n;
      }
      sm = f(val[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  void _push(int i) {
    if (laz[i] != ei()) {
      val[2 * i + 0] = g(val[2 * i + 0], laz[i]);
      val[2 * i + 1] = g(val[2 * i + 1], laz[i]);
      if (2 * i < n) {
        compose(laz[2 * i + 0], laz[i]);
        compose(laz[2 * i + 1], laz[i]);
      }
      laz[i] = ei();
    }
  }
  inline void _update(int i) { val[i] = f(val[2 * i + 0], val[2 * i + 1]); }
  inline void _apply(int i, const E& x) {
    if (x != ei()) {
      val[i] = g(val[i], x);
      if (i < n) compose(laz[i], x);
    }
  }
  inline void compose(E& a, const E& b) { a = a == ei() ? b : h(a, b); }
};

namespace SegmentTreeUtil {

template <typename T>
struct Pair {
  T first, second;
  Pair() = default;
  Pair(const T& f, const T& s) : first(f), second(s) {}
  operator T() const { return first; }
  friend ostream& operator<<(ostream& os, const Pair<T>& p) {
    os << T(p.first);
    return os;
  }
};

template <typename T>
T Mx(T a, T b) {
  return max(a, b);
}
template <typename T>
T Mn(T a, T b) {
  return min(a, b);
}
template <typename T>
T Update(T, T b) {
  return b;
}
template <typename T>
T Add(T a, T b) {
  return a + b;
}
template <typename T>
Pair<T> Psum(Pair<T> a, Pair<T> b) {
  return Pair<T>(a.first + b.first, a.second + b.second);
}
template <typename T>
Pair<T> Padd(Pair<T> a, T b) {
  return Pair<T>(a.first + a.second * b, a.second);
}
template <typename T>
Pair<T> PUpdate(Pair<T> a, T b) {
  return Pair<T>(a.second * b, a.second);
}
template <typename T>
Pair<T> Pid() {
  return Pair<T>(0, 0);
}
template <typename T>
T Zero() {
  return T(0);
}
template <typename T, T val>
T Const() {
  return val;
}

template <typename T, T MINF>
struct AddMax_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mx<T>, Add<T>, Add<T>, Const<T, MINF>, Zero<T>> {
  using base =
      LazySegmentTreeBase<T, T, Mx<T>, Add<T>, Add<T>, Const<T, MINF>, Zero<T>>;
  AddMax_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T, T INF>
struct AddMin_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mn<T>, Add<T>, Add<T>, Const<T, INF>, Zero<T>> {
  using base =
      LazySegmentTreeBase<T, T, Mn<T>, Add<T>, Add<T>, Const<T, INF>, Zero<T>>;
  AddMin_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T>
struct AddSum_LazySegmentTree
    : LazySegmentTreeBase<Pair<T>, T, Psum<T>, Padd<T>, Add<T>, Pid<T>, Zero<T>> {
  using base =
      LazySegmentTreeBase<Pair<T>, T, Psum<T>, Padd<T>, Add<T>, Pid<T>, Zero<T>>;
  AddSum_LazySegmentTree(const vector<T>& v) {
    vector<Pair<T>> w(v.size());
    for (int i = 0; i < (int)v.size(); i++) w[i] = Pair<T>(v[i], 1);
    base::init(w);
  }
};

template <typename T, T MINF>
struct UpdateMax_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mx<T>, Update<T>, Update<T>, Const<T, MINF>,
                      Const<T, MINF>> {
  using base = LazySegmentTreeBase<T, T, Mx<T>, Update<T>, Update<T>,
                               Const<T, MINF>, Const<T, MINF>>;
  UpdateMax_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T, T INF>
struct UpdateMin_LazySegmentTree
    : LazySegmentTreeBase<T, T, Mn<T>, Update<T>, Update<T>, Const<T, INF>,
                      Const<T, INF>> {
  using base = LazySegmentTreeBase<T, T, Mn<T>, Update<T>, Update<T>, Const<T, INF>,
                               Const<T, INF>>;
  UpdateMin_LazySegmentTree(const vector<T>& v) : base(v) {}
};

template <typename T, T UNUSED_VALUE>
struct UpdateSum_LazySegmentTree
    : LazySegmentTreeBase<Pair<T>, T, Psum<T>, PUpdate<T>, Update<T>, Pid<T>,
                      Const<T, UNUSED_VALUE>> {
  using base = LazySegmentTreeBase<Pair<T>, T, Psum<T>, PUpdate<T>, Update<T>,
                               Pid<T>, Const<T, UNUSED_VALUE>>;
  UpdateSum_LazySegmentTree(const vector<T>& v) {
    vector<Pair<T>> w(v.size());
    for (int i = 0; i < (int)v.size(); i++) w[i] = Pair<T>(v[i], 1);
    base::init(w);
  }
};

}  // namespace SegmentTreeUtil
using SegmentTreeUtil::AddMax_LazySegmentTree;
using SegmentTreeUtil::AddMin_LazySegmentTree;
using SegmentTreeUtil::AddSum_LazySegmentTree;
using SegmentTreeUtil::UpdateMax_LazySegmentTree;
using SegmentTreeUtil::UpdateMin_LazySegmentTree;
using SegmentTreeUtil::UpdateSum_LazySegmentTree;

/**
 * @brief 使用頻度の高い遅延セグメント木
 * @docs docs/segment-tree/lazy-segment-tree-utility.md
 */

Back to top page