Dual Segment Tree (双対セグメント木) (structure/segment-tree/dual-segment-tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-23 18:42:59+09:00
• Include: #include "structure/segment-tree/dual-segment-tree.hpp"

双対セグメント木は、遅延伝搬セグメント木の作用素モノイドのみを取り出したセグメント木です。

コンストラクタ

DualSegmentTree< Act >(Act m, int n)

作用素 m、サイズ n で初期化します。各要素には作用素の単位元 m.id() が格納されます。

計算量

• $O(n)$

Act について

Act は、次の構造体と関数を持つ構造体です。

struct Act {
  using F = ?;
  static constexpr F composition(const F &f, const F &g) {}
  static constexpr F id() {}
};

• 作用素の型 F
• 作用素の二項演算 F composition(F f, F g)
• 作用素の単位元 id()

作用素 F は、単位元 id() と比較するために != 演算子が定義されている必要があり ます。

LambdaAct について

LambdaAct は、ラムダ式を受け取って、構造体 Act のようにふるまう構造体です 。LambdaAct の引数に F composition(F f, F g)、id() の順で渡すことで初期化できます。

template< typename Composition, typename Id >
LambdaAct(Composition _composition, Id _id)

作用素 F は、単位元 id() と比較するために != 演算子が定義されている必要があります。

get

F get(int k)

k 番目の要素を x に変更します。

制約

• $0 \leq k \lt n$

計算量

• $O(\log n)$

operator[]

F operator[](int k)

k 番目の作用素を返します。

制約

• $0 \leq k \lt n$

計算量

• $O(\log n)$

apply

void apply(int l, int r, const F &f)

$l \leq k \lt r$ を満たす $k$ に対して、作用素を適用します。

制約

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

計算量

• $O(\log n)$

Depends on

• structure/class/act.hpp

Verified with

• test/verify/aoj-dsl-2-d.test.cpp
• test/verify/yosupo-range-affine-point-get.test.cpp

Code

#include "../class/act.hpp"

template <typename Act>
struct DualSegmentTree {
  using F = typename Act::F;

 private:
  int sz, height;
  vector<F> lazy;
  Act m;

  inline void propagate(int k) {
    if (lazy[k] != m.id()) {
      lazy[2 * k + 0] = m.composition(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = m.composition(lazy[2 * k + 1], lazy[k]);
      lazy[k] = m.id();
    }
  }

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

 public:
  DualSegmentTree(Act m, int n) : m(m) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, m.id());
  }

  F get(int k) {
    thrust(k += sz);
    return lazy[k];
  }

  F operator[](int k) { return get(k); }

  void apply(int a, int b, const F &f) {
    thrust(a += sz);
    thrust(b += sz - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) lazy[l] = m.composition(lazy[l], f), ++l;
      if (r & 1) --r, lazy[r] = m.composition(lazy[r], f);
    }
  }
};

#line 2 "structure/class/act.hpp"

template <typename F2, typename Composition, typename Id>
struct LambdaAct {
  using F = F2;

  F composition(const F &f, const F &g) const { return _composition(f, g); }

  F id() const { return _id(); }

  LambdaAct(Composition _composition, Id _id)
      : _composition(_composition), _id(_id) {}

 private:
  Composition _composition;
  Id _id;
};

template <typename Composition, typename Id>
LambdaAct(Composition _composition, Id _id)
    -> LambdaAct<decltype(_id()), Composition, Id>;

/*
struct Act {
  using F = ?;
  static constexpr F composition(const F &f, const F &g) {}
  static constexpr F id() const {}
};
*/
#line 2 "structure/segment-tree/dual-segment-tree.hpp"

template <typename Act>
struct DualSegmentTree {
  using F = typename Act::F;

 private:
  int sz, height;
  vector<F> lazy;
  Act m;

  inline void propagate(int k) {
    if (lazy[k] != m.id()) {
      lazy[2 * k + 0] = m.composition(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = m.composition(lazy[2 * k + 1], lazy[k]);
      lazy[k] = m.id();
    }
  }

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

 public:
  DualSegmentTree(Act m, int n) : m(m) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, m.id());
  }

  F get(int k) {
    thrust(k += sz);
    return lazy[k];
  }

  F operator[](int k) { return get(k); }

  void apply(int a, int b, const F &f) {
    thrust(a += sz);
    thrust(b += sz - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) lazy[l] = m.composition(lazy[l], f), ++l;
      if (r & 1) --r, lazy[r] = m.composition(lazy[r], f);
    }
  }
};

Back to top page