Dual Segment Tree
(data-structure/segtree/dual_segment_tree.hpp)

• View this file on GitHub
• Last update: 2024-03-02 18:46:36+09:00
• Include: #include "data-structure/segtree/dual_segment_tree.hpp"

Description

双対セグメント木は，作用素モノイド $(T, \cdot, e)$ の列に対する区間更新と一点取得を提供するデータ構造である．

空間計算量: $O(n)$

Operations

• DualSegmentTree(int n)
  • サイズnで要素がすべて単位元 $e$ の双対セグメント木を構築する
  • 時間計算量: $O(n)$
• T operator[](int k)
  • $k$ 番目の要素を返す
  • 時間計算量: $O(\log n)$
• void update(int l, int r, T x)
  • 区間 $[l, r)$ の値に $x$ を作用させる
  • 時間計算量: $O(\log n)$

Note

この実装は正しくは双対セグメント木ではなく，遅延伝搬セグメント木を半分にしたものである．本来の双対セグメント木では遅延伝搬をせずに，一点取得クエリの際に上に取りに行く．しかしこれは作用素モノイドに可換則を要求するため使い勝手が悪いので，ここでは便宜上遅延伝搬セグメント木を半分にしたものを双対セグメント木と呼んでいる．

Reference

• 双対セグメント木という概念について
• 双対セグメント木

Required by

• 2D Dual Segment Tree (data-structure/segtree/dual_segment_tree_2d.hpp)

Verified with

• test/yosupo/range_affine_point_get.test.cpp
• test/yosupo/rectangle_add_point_get.2d_dual_segtree.test.cpp

Code

#pragma once
#include <bit>
#include <vector>

template <typename M>
class DualSegmentTree {
    using T = typename M::T;

   public:
    DualSegmentTree() = default;
    explicit DualSegmentTree(int n)
        : size(std::bit_ceil((unsigned int)n)),
          height(std::bit_width((unsigned int)size) - 1),
          lazy(2 * size, M::id()) {}

    T operator[](int k) {
        k += size;
        propagate(k);
        return lazy[k];
    }

    void update(int l, int r, const T& x) {
        if (l >= r) return;
        l += size;
        r += size;
        propagate(l);
        propagate(r - 1);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lazy[l] = M::op(lazy[l], x), ++l;
            if (r & 1) --r, lazy[r] = M::op(lazy[r], x);
        }
    }

   private:
    int size, height;
    std::vector<T> lazy;

    void push(int k) {
        if (lazy[k] == M::id()) return;
        lazy[2 * k] = M::op(lazy[2 * k], lazy[k]);
        lazy[2 * k + 1] = M::op(lazy[2 * k + 1], lazy[k]);
        lazy[k] = M::id();
    }

    void propagate(int k) {
        for (int i = height; i > 0; --i) push(k >> i);
    }
};

#line 2 "data-structure/segtree/dual_segment_tree.hpp"
#include <bit>
#include <vector>

template <typename M>
class DualSegmentTree {
    using T = typename M::T;

   public:
    DualSegmentTree() = default;
    explicit DualSegmentTree(int n)
        : size(std::bit_ceil((unsigned int)n)),
          height(std::bit_width((unsigned int)size) - 1),
          lazy(2 * size, M::id()) {}

    T operator[](int k) {
        k += size;
        propagate(k);
        return lazy[k];
    }

    void update(int l, int r, const T& x) {
        if (l >= r) return;
        l += size;
        r += size;
        propagate(l);
        propagate(r - 1);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lazy[l] = M::op(lazy[l], x), ++l;
            if (r & 1) --r, lazy[r] = M::op(lazy[r], x);
        }
    }

   private:
    int size, height;
    std::vector<T> lazy;

    void push(int k) {
        if (lazy[k] == M::id()) return;
        lazy[2 * k] = M::op(lazy[2 * k], lazy[k]);
        lazy[2 * k + 1] = M::op(lazy[2 * k + 1], lazy[k]);
        lazy[k] = M::id();
    }

    void propagate(int k) {
        for (int i = height; i > 0; --i) push(k >> i);
    }
};

Back to top page