hitonanode · hitonanode · Aug 24, 2025 · Aug 24, 2025
diff --git a/segmenttree/acl_beats.hpp b/segmenttree/acl_beats.hpp
@@ -1,12 +1,14 @@
 #pragma once
 #include "acl_lazysegtree.hpp"
 
-template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F),
-          F (*id)()>
+#include <algorithm>
+#include <iostream>
+
+template <class S, auto op, auto e, class F, auto mapping, auto composition, auto id>
 class segtree_beats : public atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> {
     using Base = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
     using Base::lazy_segtree;
-    void all_apply(int k, F f) const override {
+    void all_apply(int k, F f) override {
         Base::d[k] = mapping(f, Base::d[k]);
         if (k < Base::size) {
             Base::lz[k] = composition(f, Base::lz[k]);
@@ -16,8 +18,6 @@ class segtree_beats : public atcoder::lazy_segtree<S, op, e, F, mapping, composi
 };
 
 namespace RangeChMinMaxAddSum {
-#include <algorithm>
-
 template <typename Num> inline Num second_lowest(Num a, Num a2, Num c, Num c2) noexcept {
     assert(a <= a2); // a < a2 or a == a2 == INF
     assert(c <= c2); // c < c2 or c == c2 == -INF

diff --git a/segmenttree/acl_lazysegtree.hpp b/segmenttree/acl_lazysegtree.hpp
@@ -5,21 +5,32 @@
 #include <intrin.h>
 #endif
 
+#if __cplusplus >= 202002L
+#include <bit>
+#endif
+
 namespace atcoder {
 
 namespace internal {
 
-// @param n `0 <= n`
-// @return minimum non-negative `x` s.t. `n <= 2**x`
-int ceil_pow2(int n) {
-    int x = 0;
-    while ((1U << x) < (unsigned int)(n)) x++;
+#if __cplusplus >= 202002L
+
+using std::bit_ceil;
+
+#else
+
+// @return same with std::bit::bit_ceil
+unsigned int bit_ceil(unsigned int n) {
+    unsigned int x = 1;
+    while (x < (unsigned int)(n)) x *= 2;
     return x;
 }
 
+#endif
+
 // @param n `1 <= n`
-// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
-int bsf(unsigned int n) {
+// @return same with std::bit::countr_zero
+int countr_zero(unsigned int n) {
 #ifdef _MSC_VER
     unsigned long index;
     _BitScanForward(&index, n);
@@ -29,6 +40,14 @@ int bsf(unsigned int n) {
 #endif
 }
 
+// @param n `1 <= n`
+// @return same with std::bit::countr_zero
+constexpr int countr_zero_constexpr(unsigned int n) {
+    int x = 0;
+    while (!(n & (1 << x))) x++;
+    return x;
+}
+
 } // namespace internal
 
 } // namespace atcoder
@@ -37,24 +56,31 @@ int bsf(unsigned int n) {
 #ifndef ATCODER_LAZYSEGTREE_HPP
 #define ATCODER_LAZYSEGTREE_HPP 1
 
-#include <algorithm>
 #include <cassert>
-#include <iostream>
+#include <functional>
 #include <vector>
 
-// #include "atcoder/internal_bit"
+#include "atcoder/internal_bit"
 
 namespace atcoder {
 
-template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F),
-          F (*id)()>
+template <class S, auto op, auto e, class F, auto mapping, auto composition, auto id>
 struct lazy_segtree {
+    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
+                  "op must work as S(S, S)");
+    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>, "e must work as S()");
+    static_assert(std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
+                  "mapping must work as S(F, S)");
+    static_assert(std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
+                  "composition must work as F(F, F)");
+    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>, "id must work as F()");
+
 public:
     lazy_segtree() : lazy_segtree(0) {}
     explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
     explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
-        log = internal::ceil_pow2(_n);
-        size = 1 << log;
+        size = (int)internal::bit_ceil((unsigned int)(_n));
+        log = internal::countr_zero((unsigned int)size);
         d = std::vector<S>(2 * size, e());
         lz = std::vector<F>(size, id());
         for (int i = 0; i < _n; i++) d[size + i] = v[i];
@@ -69,14 +95,14 @@ struct lazy_segtree {
         for (int i = 1; i <= log; i++) update(p >> i);
     }
 
-    S get(int p) const {
+    S get(int p) {
         assert(0 <= p && p < _n);
         p += size;
         for (int i = log; i >= 1; i--) push(p >> i);
         return d[p];
     }
 
-    S prod(int l, int r) const {
+    S prod(int l, int r) {
         assert(0 <= l && l <= r && r <= _n);
         if (l == r) return e();
 
@@ -99,7 +125,7 @@ struct lazy_segtree {
         return op(sml, smr);
     }
 
-    S all_prod() const { return d[1]; }
+    S all_prod() { return d[1]; }
 
     void apply(int p, F f) {
         assert(0 <= p && p < _n);
@@ -138,10 +164,10 @@ struct lazy_segtree {
         }
     }
 
-    template <bool (*g)(S)> int max_right(int l) const {
+    template <bool (*g)(S)> int max_right(int l) {
         return max_right(l, [](S x) { return g(x); });
     }
-    template <class G> int max_right(int l, G g) const {
+    template <class G> int max_right(int l, G g) {
         assert(0 <= l && l <= _n);
         assert(g(e()));
         if (l == _n) return _n;
@@ -167,10 +193,10 @@ struct lazy_segtree {
         return _n;
     }
 
-    template <bool (*g)(S)> int min_left(int r) const {
+    template <bool (*g)(S)> int min_left(int r) {
         return min_left(r, [](S x) { return g(x); });
     }
-    template <class G> int min_left(int r, G g) const {
+    template <class G> int min_left(int r, G g) {
         assert(0 <= r && r <= _n);
         assert(g(e()));
         if (r == 0) return 0;
@@ -198,23 +224,23 @@ struct lazy_segtree {
 
 protected:
     int _n, size, log;
-    mutable std::vector<S> d;
-    mutable std::vector<F> lz;
+    std::vector<S> d;
+    std::vector<F> lz;
 
-    void update(int k) const { d[k] = op(d[2 * k], d[2 * k + 1]); }
-    virtual void all_apply(int k, F f) const {
+    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
+    virtual void all_apply(int k, F f) {
         d[k] = mapping(f, d[k]);
         if (k < size) lz[k] = composition(f, lz[k]);
     }
-    void push(int k) const {
+    void push(int k) {
         all_apply(2 * k, lz[k]);
         all_apply(2 * k + 1, lz[k]);
         lz[k] = id();
     }
 };
 } // namespace atcoder
 #endif // ATCODER_LAZYSEGTREE_HPP
-// Reference: https://atcoder.github.io/ac-library/document_ja/lazysegtree.html
+// Reference: https://atcoder.github.io/ac-library/production/document_ja/lazysegtree.html
 //            https://betrue12.hateblo.jp/entry/2020/09/22/194541
 //            https://betrue12.hateblo.jp/entry/2020/09/23/005940
 /*

diff --git a/segmenttree/acl_segtree.hpp b/segmenttree/acl_segtree.hpp
@@ -5,21 +5,32 @@
 #include <intrin.h>
 #endif
 
+#if __cplusplus >= 202002L
+#include <bit>
+#endif
+
 namespace atcoder {
 
 namespace internal {
 
-// @param n `0 <= n`
-// @return minimum non-negative `x` s.t. `n <= 2**x`
-int ceil_pow2(int n) {
-    int x = 0;
-    while ((1U << x) < (unsigned int)(n)) x++;
+#if __cplusplus >= 202002L
+
+using std::bit_ceil;
+
+#else
+
+// @return same with std::bit::bit_ceil
+unsigned int bit_ceil(unsigned int n) {
+    unsigned int x = 1;
+    while (x < (unsigned int)(n)) x *= 2;
     return x;
 }
 
+#endif
+
 // @param n `1 <= n`
-// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
-int bsf(unsigned int n) {
+// @return same with std::bit::countr_zero
+int countr_zero(unsigned int n) {
 #ifdef _MSC_VER
     unsigned long index;
     _BitScanForward(&index, n);
@@ -38,21 +49,24 @@ int bsf(unsigned int n) {
 #ifndef ATCODER_SEGTREE_HPP
 #define ATCODER_SEGTREE_HPP 1
 
-#include <algorithm>
 #include <cassert>
+#include <functional>
 #include <vector>
 
 // #include "atcoder/internal_bit"
 
 namespace atcoder {
+template <class S, auto op, auto e> struct segtree {
+    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
+                  "op must work as S(S, S)");
+    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>, "e must work as S()");
 
-template <class S, S (*op)(S, S), S (*e)()> struct segtree {
 public:
     segtree() : segtree(0) {}
     explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
     explicit segtree(const std::vector<S> &v) : _n(int(v.size())) {
-        log = internal::ceil_pow2(_n);
-        size = 1 << log;
+        size = (int)internal::bit_ceil((unsigned int)(_n));
+        log = internal::countr_zero((unsigned int)size);
         d = std::vector<S>(2 * size, e());
         for (int i = 0; i < _n; i++) d[size + i] = v[i];
         for (int i = size - 1; i >= 1; i--) { update(i); }
@@ -152,7 +166,7 @@ template <class S, S (*op)(S, S), S (*e)()> struct segtree {
 
 #endif // ATCODER_SEGTREE_HPP
 
-// Reference: https://atcoder.github.io/ac-library/document_ja/segtree.html
+// Reference: https://atcoder.github.io/ac-library/production/document_ja/segtree.html
 /* usage:
 struct S {
     long long su;

diff --git a/segmenttree/acl_segtree.md b/segmenttree/acl_segtree.md
@@ -0,0 +1,22 @@
+---
+title: Segtree (based on atcoder::segtree)
+documentation_of: ./acl_segtree.hpp
+---
+
+ACL-based segtree
+
+## Example
+
+```cpp
+struct S {};
+S op(S l, S r) {
+    return {};
+}
+S e() { return {}; };
+vector<S> A;
+atcoder::segtree<S, op, e> seg(A);
+```
+
+## Link
+
+- [ACL reference](https://atcoder.github.io/ac-library/production/document_ja/segtree.html)
diff --git a/segmenttree/binary_indexed_tree_2d.hpp b/segmenttree/binary_indexed_tree_2d.hpp
@@ -1,8 +1,7 @@
 #pragma once
 #include <array>
 
-// CUT begin
-// 2-dimentional 1-indexed BIT (i : [1, lenX][1, lenY])
+// 2-dimensional 1-indexed BIT (i : [1, lenX][1, lenY])
 template <typename T, int lenX, int lenY> struct BIT_2D {
     std::array<T, (lenX + 1) * (lenY + 1)> val;
     constexpr static int M = lenY + 1;