区間更新 + 区間和クエリ solver (Range Update Range Sum Query Solver)
(src/data-structure/segment-tree/presets/range-update-range-sum-query-solver.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/data-structure/segment-tree/presets/range-update-range-sum-query-solver.hpp"

数列に対する区間更新クエリと区間和クエリを処理するデータ構造。

内部ではセグメント木を用いているため、詳細な仕様などはそちらのドキュメントに追従する。

コンストラクタ

(1) RangeUpdateRangeSumQuerySolver< T, ID >(usize n)
(2) RangeUpdateRangeSumQuerySolver< T, ID >(usize n, T v)
(3) RangeUpdateRangeSumQuerySolver< T, ID >(std::vector< T > vs)

ID について

更新の自然な単位元は存在しないため、ID として「更新クエリとして与えられることのない型 T の値」を与える必要がある。

Depends on

• int alias (src/cpp-template/header/int-alias.hpp)
• rep 構造体 (src/cpp-template/header/rep.hpp)
• size alias (src/cpp-template/header/size-alias.hpp)
• src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp
• src/data-structure/segment-tree/presets/monoid/operator-structure-update.hpp
• src/data-structure/segment-tree/presets/monoid/value-structure-sum.hpp
• 区間更新+区間取得 セグメント木 (Lazy Segment Tree) (src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp)
• 値を表現するために必要な最小のbit幅 (bit_width) (src/utility/bit/bit-width.hpp)
• 最下位bitから連続する 0 の数 (counting trailing 0s, countr_zero) (src/utility/bit/count-trailing-0s.hpp)
• 立っている bit の数 (population count, popcount) (src/utility/bit/popcount.hpp)

Verified with

• test/aoj/dsl_2_i.test.cpp

Code

#pragma once

#include "src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp"
#include "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp"

namespace luz {

  template < typename T, T ID >
  using RangeUpdateRangeSumQuerySolver = LazySegmentTree<
      monoid::RangeUpdateRangeSumQueryMonoid< T, ID > >;

} // namespace luz

#line 2 "src/data-structure/segment-tree/presets/range-update-range-sum-query-solver.hpp"

#line 2 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 2 "src/data-structure/segment-tree/presets/monoid/operator-structure-update.hpp"

namespace luz::monoid {

  template < typename T, T ID >
  class RangeUpdateQueryMonoid {

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return b == ID ? a : b;
    }

    static constexpr T identity() {
      return ID;
    }
  };

} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/presets/monoid/value-structure-sum.hpp"

namespace luz::monoid {

  template < typename T >
  class RangeSumQueryMonoid {

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return a + b;
    }

    static constexpr T identity() {
      return T();
    }
  };

} // namespace luz::monoid
#line 6 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp"

namespace luz::monoid {

  template < typename T, T ID >
  class RangeUpdateRangeSumQueryMonoid {

    class node_type {
      using F = node_type;

     public:
      T value;
      usize count;

      node_type(): value(), count() {}
      node_type(T v, usize c): value(v), count(c) {}

      F operator+(const F &b) {
        return F(value + b.value, count + b.count);
      }
    };

    using V  = RangeSumQueryMonoid< node_type >;
    using VT = typename V::value_type;
    using O  = RangeUpdateQueryMonoid< T, ID >;
    using OT = typename O::value_type;

   public:
    using value_structure    = V;
    using operator_structure = O;

    static constexpr VT operation(VT a, OT b) {
      return b == ID ? a : VT(b * a.count, a.count);
    }
  };

} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/utility/bit/bit-width.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/utility/bit/popcount.hpp"

#line 5 "src/utility/bit/popcount.hpp"

#include <cassert>

namespace luz {

  usize popcount(u64 x) {
    assert(__cplusplus <= 201703L);

#ifdef __GNUC__
    return __builtin_popcountll(x);
#endif

    x -= (x >> 1) & 0x5555555555555555;
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f;
    return x * 0x0101010101010101 >> 56 & 0x7f;
  }

} // namespace luz
#line 6 "src/utility/bit/bit-width.hpp"

#line 8 "src/utility/bit/bit-width.hpp"

namespace luz {

  usize bit_width(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 0;
    }

#ifdef __GNUC__
    return 64 - __builtin_clzll(x);
#endif

    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return popcount(x);
  }

} // namespace luz
#line 2 "src/utility/bit/count-trailing-0s.hpp"

#line 6 "src/utility/bit/count-trailing-0s.hpp"

#line 8 "src/utility/bit/count-trailing-0s.hpp"

namespace luz {

  usize countr_zero(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 64;
    }

#ifdef __GNUC__
    return __builtin_ctzll(x);
#endif

    return popcount((x & -x) - 1);
  }

} // namespace luz
#line 7 "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp"

#line 9 "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp"
#include <vector>

namespace luz {

  template < class combined_structure >
  class RangeMappingRangeFoldSegmentTree {
    using C  = combined_structure;
    using V  = typename C::value_structure;
    using VT = typename V::value_type;
    using O  = typename C::operator_structure;
    using OT = typename O::value_type;

    class node_type {
     public:
      VT value;
      OT lazy;

      node_type(const VT value_, const OT lazy_)
          : value(value_),
            lazy(lazy_) {}

      VT get() {
        return C::operation(value, lazy);
      }
    };

    std::vector< node_type > tree;

    void evaluate_lazy(OT &x, const OT &y) {
      x = O::operation(x, y);
    }

    void recalc(usize index) {
      tree[index].value = V::operation(tree[index << 1 | 0].get(),
                                       tree[index << 1 | 1].get());
    }

    void recalc_bound(usize index) {
      if (index == 0) return;

      const usize l = countr_zero(index) + 1;
      const usize r = bit_width(index);
      for (usize i: rep(l, r)) {
        recalc(index >> i);
      }
    }

    void propagate(const usize index) {
      evaluate_lazy(tree[index << 1 | 0].lazy, tree[index].lazy);
      evaluate_lazy(tree[index << 1 | 1].lazy, tree[index].lazy);
      tree[index].lazy = O::identity();
    }

    void propagate_bound(const usize index) {
      if (index == 0) return;

      const usize l = countr_zero(index) + 1;
      const usize r = bit_width(index);
      for (usize i: rrep(l, r)) {
        propagate(index >> i);
      }
    }

   public:
    using value_type = VT;

    RangeMappingRangeFoldSegmentTree() = default;

    explicit RangeMappingRangeFoldSegmentTree(const usize n)
        : tree(n * 2, node_type(V::identity(), O::identity())) {}

    explicit RangeMappingRangeFoldSegmentTree(const usize n,
                                              const VT v)
        : RangeMappingRangeFoldSegmentTree(n) {
      build(std::vector< VT >(n, v));
    }

    explicit RangeMappingRangeFoldSegmentTree(
        const std::vector< VT > &vs)
        : RangeMappingRangeFoldSegmentTree(vs.size()) {
      build(vs);
    }

    void build(const std::vector< VT > &vs) {
      usize n = vs.size();
      assert(2 * n == tree.size());
      for (usize i: rep(0, n)) {
        tree[i + n] = node_type(vs[i], O::identity());
      }
      for (usize index: rrep(1, n)) {
        recalc(index);
      }
    }

    usize size() const {
      return tree.size() / 2;
    }

    void set(usize index, const VT x) {
      assert(index < size());
      index += size();

      const usize l = 1;
      const usize r = bit_width(index);
      for (usize i: rrep(l, r)) {
        propagate(index >> i);
      }

      tree[index] = node_type(x, O::identity());

      for (usize i: rep(l, r)) {
        recalc(index >> i);
      }
    }

    void apply(usize index, const OT &x) {
      return apply(index, index + 1, x);
    }

    void apply(usize first, usize last, const OT &x) {
      assert(first <= last);
      assert(last <= size());

      first += size();
      last += size();

      propagate_bound(first);
      propagate_bound(last);

      const usize c_first = first;
      const usize c_last  = last;

      while (first != last) {
        if (first & 1) {
          evaluate_lazy(tree[first].lazy, x);
          first += 1;
        }
        first >>= 1;

        if (last & 1) {
          last -= 1;
          evaluate_lazy(tree[last].lazy, x);
        }
        last >>= 1;
      }

      recalc_bound(c_first);
      recalc_bound(c_last);
    }

    VT fold(usize index) {
      return fold(index, index + 1);
    }

    VT fold(usize first, usize last) {
      assert(first <= last);
      assert(last <= size());

      first += size();
      last += size();

      propagate_bound(first);
      recalc_bound(first);
      propagate_bound(last);
      recalc_bound(last);

      VT fold_l = V::identity();
      VT fold_r = V::identity();

      while (first != last) {
        if (first & 1) {
          fold_l = V::operation(fold_l, tree[first].get());
          first += 1;
        }
        first >>= 1;

        if (last & 1) {
          last -= 1;
          fold_r = V::operation(tree[last].get(), fold_r);
        }
        last >>= 1;
      }

      return V::operation(fold_l, fold_r);
    }

    VT fold_all() {
      return (size() ? tree[1].get() : V::identity());
    }
  };

  template < class combined_structure >
  using LazySegmentTree =
      RangeMappingRangeFoldSegmentTree< combined_structure >;

} // namespace luz
#line 5 "src/data-structure/segment-tree/presets/range-update-range-sum-query-solver.hpp"

namespace luz {

  template < typename T, T ID >
  using RangeUpdateRangeSumQuerySolver = LazySegmentTree<
      monoid::RangeUpdateRangeSumQueryMonoid< T, ID > >;

} // namespace luz

Back to top page