Dual Segment Tree
(segment-tree/dual-segment-tree.hpp)

• View this file on GitHub
• Last update: 2025-10-17 21:43:09+09:00
• Include: #include "segment-tree/dual-segment-tree.hpp"

モノイド $(T,\cdot,e)$ に対するデータ構造．

• 実際は $\cdot$ が $T\times T$ 上全体で定義されていなくても，計算で出てくる範囲で定義されていれば構わない．

長さ $N$ の $T$ の列 $A=(A_0,A_1,\dots,A_{N-1})$ に対し，空間計算量 $\Theta(N)$ のもとで以下の操作を行う．

• 区間乗算：$O(\log N)$ 時間
• 一点取得：$O(\log N)$ 時間

ただし乗算は左から掛けるものとする．

すなわち $[l,r)$ への $x$ の乗算では以下を行う．

• $i\in[l,r)$ に対し $A_i\leftarrow x\cdot A_i$ とする．

仕組み

通常のセグメント木では，適当な区間についてそこに含まれる要素の総積を管理していた．

双対セグメント木では，適当な区間についてそこに含まれる要素全てに共通して乗算される値を管理する．

また通常のセグメント木では下から上に値を伝播させていたが，双対セグメント木では上から下に値を伝播させる．

演算が可換なとき

区間乗算は通常のセグメント木での区間総積と，一点取得は通常のセグメント木での一点更新と同様にすればよい．

演算が非可換なとき

値を更新する前に，その親の情報を子に伝播しておく必要がある．

子への伝播を行うべき区間は，更新する区間を分割したときに端にくる区間の上にあるもののみ．

従って $O(\log N)$ 時間で行える．

Verified with

• verify/segment-tree/LC_range_affine_point_get.test.cpp

Code

#pragma once

template <class F, F (*op)(F, F), F (*e)()>
struct DualSegmentTree {
 private:
  int _n, size, log;
  vector<F> lz;

 public:
  DualSegmentTree() : DualSegmentTree(0) {}
  explicit DualSegmentTree(int n) : DualSegmentTree(vector<F>(n, e())) {}
  explicit DualSegmentTree(const vector<F> &v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    lz = vector<F>(2 * size, e());
    for (int i = 0; i < _n; i++) lz[size + i] = v[i];
  }
  void set(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    lz[p] = f;
  }
  F get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    return lz[p];
  }
  vector<F> all_get() {
    for (int i = 1; i < size; i++) push(i);
    return vector<F>(lz.begin() + size, lz.begin() + (size + _n));
  }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    inner_apply(p, f);
  }
  void apply(int l, int r, F f) {
    if (l >= r) return;
    assert(0 <= l && l <= r && r <= _n);
    l += size, r += size;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    while (l < r) {
      if ((l & 1) != 0) inner_apply(l++, f);
      if ((r & 1) != 0) inner_apply(--r, f);
      l >>= 1, r >>= 1;
    }
  }

 private:
  void push(int k) {
    inner_apply(2 * k, lz[k]);
    inner_apply(2 * k + 1, lz[k]);
    lz[k] = e();
  }
  void inner_apply(int k, F f) { lz[k] = op(f, lz[k]); }
};

/**
 * @brief Dual Segment Tree
 * @docs docs/segment-tree/dual-segment-tree.md
 */

#line 2 "segment-tree/dual-segment-tree.hpp"

template <class F, F (*op)(F, F), F (*e)()>
struct DualSegmentTree {
 private:
  int _n, size, log;
  vector<F> lz;

 public:
  DualSegmentTree() : DualSegmentTree(0) {}
  explicit DualSegmentTree(int n) : DualSegmentTree(vector<F>(n, e())) {}
  explicit DualSegmentTree(const vector<F> &v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    lz = vector<F>(2 * size, e());
    for (int i = 0; i < _n; i++) lz[size + i] = v[i];
  }
  void set(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    lz[p] = f;
  }
  F get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    return lz[p];
  }
  vector<F> all_get() {
    for (int i = 1; i < size; i++) push(i);
    return vector<F>(lz.begin() + size, lz.begin() + (size + _n));
  }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    inner_apply(p, f);
  }
  void apply(int l, int r, F f) {
    if (l >= r) return;
    assert(0 <= l && l <= r && r <= _n);
    l += size, r += size;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    while (l < r) {
      if ((l & 1) != 0) inner_apply(l++, f);
      if ((r & 1) != 0) inner_apply(--r, f);
      l >>= 1, r >>= 1;
    }
  }

 private:
  void push(int k) {
    inner_apply(2 * k, lz[k]);
    inner_apply(2 * k + 1, lz[k]);
    lz[k] = e();
  }
  void inner_apply(int k, F f) { lz[k] = op(f, lz[k]); }
};

/**
 * @brief Dual Segment Tree
 * @docs docs/segment-tree/dual-segment-tree.md
 */

Back to top page