Dual Segment Tree - 双対セグメント木
(Library/DataStructure/DualSegmentTree.hpp)

• View this file on GitHub
• Last update: 2026-02-08 19:12:56+09:00
• Include: #include "Library/DataStructure/DualSegmentTree.hpp"

Dual Segment Tree - 双対セグメント木

長さ $N$ の数列 $A = (A_1, \dots, A_N)$ に対し、区間更新・一点取得クエリを効率的に行うことができるデータ構造です。

更新操作はモノイド $O$ である必要があります。以下、操作モノイドの単位元を $e_O$ とします。

Function

Constructor

DualSegmentTree(int size, H composite, const OperatorMonoid &operator_identity, bool zero_index = false)

• セグメント木の数列 $A$ を長さ $n$ で初期化します。初期値はすべて $e_O$ です。
• composite には遅延評価を合成する演算 $\odot : O \times O \rightarrow O$ を渡します。
  • 区間加算 : [](int x, int y){return x + y;}
  • 区間代入 : [](int x, int y){return y;}
• operator_identity には操作モノイド $O$ の単位元 $e_O$ を渡します。
• zero_index に true を指定すると、セグメント木にアクセスする添え字を 0-index でアクセスすることができます。デフォルトでは 1-index です。
  • 本ドキュメントでは添え字に関する制約は 1-index で示します。

制約

• $1 \le n \le 10^6$
• composite は $O \times O \rightarrow O$ の関数
• $e_O$ は $O$ の単位元

計算量

• $\textrm{O}(n)$

---

Set

void Set(int index, OperatorMonoid value)

• $A_i$ に初期値 $v$ を代入します。（index が $i$ に対応）
• 初期値を設定するために使用します。

制約

• $1 \le i \le n$
• $v \in O$

計算量

• $\textrm{O}(1)$

---

Update

void Update(int left, int right, OperatorMonoid operation)

• 半開区間 $[l, r)$ に対して区間更新クエリを実行します。（left が $l$、right が $r$ に対応）
• 区間内の各要素に対して operation を適用します。

制約

• $1 \le l \le n$
• $l \le r \le n + 1$
• $operation \in O$

計算量

• $\textrm{O}(\log n)$

---

Product

OperatorMonoid Product(int index)

• $A_i$ を取得します。（index が $i$ に対応）
• これまでに適用されたすべての操作の合成結果を返します。

制約

• $1 \le i \le n$

計算量

• $\textrm{O}(\log n)$

---

Depends on

• Library/Common.hpp

Verified with

• verify/LC-RangeAffinePointGet.test.cpp

Code

#include "../Common.hpp"

template<typename OperatorMonoid>
class DualSegmentTree{
    public:
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
    
    DualSegmentTree(int size, H composite, const OperatorMonoid &operator_identity, bool zero_index = false)
    : h(composite), om1_(operator_identity), zeroindex_(zero_index){
        size_ = 1;
        while(size_ < size) size_ <<= 1;
        offset_ = size_ - 1;
        lazy_.resize(2 * size_, om1_);
        is_identity_.resize(2 * size_, true);
    }

    void Set(int index, OperatorMonoid value){
        Validate(index + zeroindex_);
        lazy_[offset_ + index + zeroindex_] = value;
    }

    void Update(int left, int right, OperatorMonoid operation){
        Validate(left + zeroindex_);
        Validate(right + zeroindex_ - 1);
        RecursiveUpdate(left + zeroindex_, right + zeroindex_, operation, 1, size_ + 1, 1);
    }

    OperatorMonoid Product(int index){
        Validate(index + zeroindex_);
        return RecursiveProduct(index + zeroindex_, 1, size_ + 1, 1);
    }

    private:
    int size_, offset_, zeroindex_;
    vector<OperatorMonoid> lazy_;
    vector<bool> is_identity_;
    const H h;
    const OperatorMonoid om1_;

    inline void Validate(int x){
        assert(1 <= x && x <= size_);
    }

    void Evaluate(int k){
        if(is_identity_[k]) return;
        if(k < size_){
            lazy_[k * 2 + 0] = h(lazy_[k * 2 + 0], lazy_[k]);
            is_identity_[k * 2 + 0] = false;
            lazy_[k * 2 + 1] = h(lazy_[k * 2 + 1], lazy_[k]);
            is_identity_[k * 2 + 1] = false;
            lazy_[k] = om1_;
            is_identity_[k] = true;
        }
    }

    void RecursiveUpdate(int ul, int ur, OperatorMonoid x, int left, int right, int cell){
        Evaluate(cell);
        if(ul <= left && right <= ur){
            lazy_[cell] = h(lazy_[cell], x);
            is_identity_[cell] = false;
            Evaluate(cell);
        }
        else if(ul < right && left < ur){
            int mid = (left + right) / 2;
            RecursiveUpdate(ul, ur, x, left, mid, cell * 2 + 0);
            RecursiveUpdate(ul, ur, x, mid, right, cell * 2 + 1);
        }
    }
    
    OperatorMonoid RecursiveProduct(int q, int left, int right, int cell){
        Evaluate(cell);
        if(q == left && right - left == 1) return lazy_[cell];
        int mid = (left + right) / 2;
        if(q < mid) return RecursiveProduct(q, left, mid, cell * 2 + 0);
        else return RecursiveProduct(q, mid, right, cell * 2 + 1);
    }
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/DualSegmentTree.hpp"

template<typename OperatorMonoid>
class DualSegmentTree{
    public:
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
    
    DualSegmentTree(int size, H composite, const OperatorMonoid &operator_identity, bool zero_index = false)
    : h(composite), om1_(operator_identity), zeroindex_(zero_index){
        size_ = 1;
        while(size_ < size) size_ <<= 1;
        offset_ = size_ - 1;
        lazy_.resize(2 * size_, om1_);
        is_identity_.resize(2 * size_, true);
    }

    void Set(int index, OperatorMonoid value){
        Validate(index + zeroindex_);
        lazy_[offset_ + index + zeroindex_] = value;
    }

    void Update(int left, int right, OperatorMonoid operation){
        Validate(left + zeroindex_);
        Validate(right + zeroindex_ - 1);
        RecursiveUpdate(left + zeroindex_, right + zeroindex_, operation, 1, size_ + 1, 1);
    }

    OperatorMonoid Product(int index){
        Validate(index + zeroindex_);
        return RecursiveProduct(index + zeroindex_, 1, size_ + 1, 1);
    }

    private:
    int size_, offset_, zeroindex_;
    vector<OperatorMonoid> lazy_;
    vector<bool> is_identity_;
    const H h;
    const OperatorMonoid om1_;

    inline void Validate(int x){
        assert(1 <= x && x <= size_);
    }

    void Evaluate(int k){
        if(is_identity_[k]) return;
        if(k < size_){
            lazy_[k * 2 + 0] = h(lazy_[k * 2 + 0], lazy_[k]);
            is_identity_[k * 2 + 0] = false;
            lazy_[k * 2 + 1] = h(lazy_[k * 2 + 1], lazy_[k]);
            is_identity_[k * 2 + 1] = false;
            lazy_[k] = om1_;
            is_identity_[k] = true;
        }
    }

    void RecursiveUpdate(int ul, int ur, OperatorMonoid x, int left, int right, int cell){
        Evaluate(cell);
        if(ul <= left && right <= ur){
            lazy_[cell] = h(lazy_[cell], x);
            is_identity_[cell] = false;
            Evaluate(cell);
        }
        else if(ul < right && left < ur){
            int mid = (left + right) / 2;
            RecursiveUpdate(ul, ur, x, left, mid, cell * 2 + 0);
            RecursiveUpdate(ul, ur, x, mid, right, cell * 2 + 1);
        }
    }
    
    OperatorMonoid RecursiveProduct(int q, int left, int right, int cell){
        Evaluate(cell);
        if(q == left && right - left == 1) return lazy_[cell];
        int mid = (left + right) / 2;
        if(q < mid) return RecursiveProduct(q, left, mid, cell * 2 + 0);
        else return RecursiveProduct(q, mid, right, cell * 2 + 1);
    }
};

Back to top page