Dual segment tree (tools/dual_segtree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-03-23 00:38:31+09:00
• Include: #include "tools/dual_segtree.hpp"

It is a pair of a monoid $(S, \cdot, e)$ and a sequence $(a_0, a_1, \ldots, a_{n - 1})$ on $S$. It provides the following operations.

• It can update $a_i$ to $x \cdot a_i$ for all $i$ such that $l \leq i < r$, in $O(\log n)$ time.
• It can access $a_i$ in $O(\log n)$ time.

License

• CC0

Author

• anqooqie

Constructor

dual_segtree<M> a(int n);

It creates a sequence $(a_0, a_1, \ldots, a_{n - 1})$ filled in M::e().

Constraints

• For all $x$ in typename M::T, $y$ in typename M::T and $z$ in typename M::T, M::op(M::op(x, y), z) $=$ M::op(x, M::op(y, z)).
• For all $x$ in typename M::T, M::op(M::e(), x) $=$ M::op(x, M::e()) $=$ x.

Time Complexity

• $O(n)$

apply

void a.apply(int l, int r, typename M::T x);

For all $i$ such that $l \leq i < r$, it updates $a_i$ to M::op$(x, a_i)$.

Constraints

• $0 \leq l \leq r \leq n$

Time Complexity

• $O(\log n)$

get

typename M::T a.get(int i);

It returns $a_i$.

Constraints

• $0 \leq i < n$

Time Complexity

• $O(\log n)$

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lceil \log_2(x) \right\rceil$ (tools/ceil_log2.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
• $2^x$ (tools/pow2.hpp)

Verified with

• tests/dual_segtree.test.cpp

Code

#ifndef TOOLS_DUAL_SEGTREE_HPP
#define TOOLS_DUAL_SEGTREE_HPP

#include <vector>
#include "tools/ceil_log2.hpp"
#include "tools/pow2.hpp"

namespace tools {

  template <typename M>
  class dual_segtree {
    using T = typename M::T;
    int height;
    ::std::vector<T> lazy;

    void propagate(const int node_id) {
      if(this->lazy[node_id] == M::e()) return;
      this->lazy[(node_id << 1) | 0] = M::op(this->lazy[node_id], this->lazy[(node_id << 1) | 0]);
      this->lazy[(node_id << 1) | 1] = M::op(this->lazy[node_id], this->lazy[(node_id << 1) | 1]);
      this->lazy[node_id] = M::e();
    }

    void thrust(const int node_id) {
      for (int h = this->height; h > 0; --h) {
        this->propagate(node_id >> h);
      }
    }

    int capacity() const {
      return this->lazy.size() / 2;
    }

  public:
    dual_segtree() = default;
    explicit dual_segtree(const int n) :
      height(::tools::ceil_log2(n)),
      lazy(::tools::pow2(this->height + 1), M::e()) {
    }

    void apply(const int a, const int b, const T& x) {
      if(a >= b) return;

      const int a_id = a + this->capacity();
      const int b_id = b + this->capacity() - 1;

      this->thrust(a_id);
      this->thrust(b_id);

      for (int l = a_id, r = b_id + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) {
          this->lazy[l] = M::op(x, this->lazy[l]);
          ++l;
        }
        if (r & 1) {
          --r;
          this->lazy[r] = M::op(x, this->lazy[r]);
        }
      }
    }

    T get(const int a) {
      const int node_id = a + this->capacity();
      this->thrust(node_id);
      return this->lazy[node_id];
    }
  };
}

#endif

#line 1 "tools/dual_segtree.hpp"



#include <vector>
#line 1 "tools/ceil_log2.hpp"



#include <cassert>
#line 1 "tools/bit_width.hpp"



#include <bit>
#line 6 "tools/bit_width.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/pow2.hpp"



#line 5 "tools/pow2.hpp"
#include <cstddef>

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 7 "tools/dual_segtree.hpp"

namespace tools {

  template <typename M>
  class dual_segtree {
    using T = typename M::T;
    int height;
    ::std::vector<T> lazy;

    void propagate(const int node_id) {
      if(this->lazy[node_id] == M::e()) return;
      this->lazy[(node_id << 1) | 0] = M::op(this->lazy[node_id], this->lazy[(node_id << 1) | 0]);
      this->lazy[(node_id << 1) | 1] = M::op(this->lazy[node_id], this->lazy[(node_id << 1) | 1]);
      this->lazy[node_id] = M::e();
    }

    void thrust(const int node_id) {
      for (int h = this->height; h > 0; --h) {
        this->propagate(node_id >> h);
      }
    }

    int capacity() const {
      return this->lazy.size() / 2;
    }

  public:
    dual_segtree() = default;
    explicit dual_segtree(const int n) :
      height(::tools::ceil_log2(n)),
      lazy(::tools::pow2(this->height + 1), M::e()) {
    }

    void apply(const int a, const int b, const T& x) {
      if(a >= b) return;

      const int a_id = a + this->capacity();
      const int b_id = b + this->capacity() - 1;

      this->thrust(a_id);
      this->thrust(b_id);

      for (int l = a_id, r = b_id + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) {
          this->lazy[l] = M::op(x, this->lazy[l]);
          ++l;
        }
        if (r & 1) {
          --r;
          this->lazy[r] = M::op(x, this->lazy[r]);
        }
      }
    }

    T get(const int a) {
      const int node_id = a + this->capacity();
      this->thrust(node_id);
      return this->lazy[node_id];
    }
  };
}

Back to top page