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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "structure/segment-tree/dual-segment-tree.hpp"

概要

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

使い方

• DualSegmentTree(n, h, OM0): サイズ n で初期化する. ここで h は2つの区間の作用素をマージする二項演算, OM0 は作用素の単位元である.
• update(l, r, x): 区間 $[l, r)$ に作用素 x を適用する.
• operator[k]: k 番目の作用素を返す.

auto seg = get_dual_segment_tree(N, h, OM0); のようにすると decltype(h) などを用いなくてすむ.

計算量

• クエリ: $O(\log N)$

Verified with

• test/verify/aoj-dsl-2-d.test.cpp

Code

/**
 * @brief Dual-Segment-Tree(双対セグメント木)
 *
 */
template <typename E, typename H>
struct DualSegmentTree {
  int sz, height;
  vector<E> lazy;
  const H h;
  const E ei;

  DualSegmentTree(int n, const H h, const E& ei) : h(h), ei(ei) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, ei);
  }

  inline void propagate(int k) {
    if (lazy[k] != ei) {
      lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      lazy[k] = ei;
    }
  }

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

  void update(int a, int b, const E& x) {
    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] = h(lazy[l], x), ++l;
      if (r & 1) --r, lazy[r] = h(lazy[r], x);
    }
  }

  E operator[](int k) {
    thrust(k += sz);
    return lazy[k];
  }
};

template <typename E, typename H>
DualSegmentTree<E, H> get_dual_segment_tree(int N, const H& h, const E& ei) {
  return {N, h, ei};
}

#line 1 "structure/segment-tree/dual-segment-tree.hpp"
/**
 * @brief Dual-Segment-Tree(双対セグメント木)
 *
 */
template <typename E, typename H>
struct DualSegmentTree {
  int sz, height;
  vector<E> lazy;
  const H h;
  const E ei;

  DualSegmentTree(int n, const H h, const E& ei) : h(h), ei(ei) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, ei);
  }

  inline void propagate(int k) {
    if (lazy[k] != ei) {
      lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      lazy[k] = ei;
    }
  }

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

  void update(int a, int b, const E& x) {
    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] = h(lazy[l], x), ++l;
      if (r & 1) --r, lazy[r] = h(lazy[r], x);
    }
  }

  E operator[](int k) {
    thrust(k += sz);
    return lazy[k];
  }
};

template <typename E, typename H>
DualSegmentTree<E, H> get_dual_segment_tree(int N, const H& h, const E& ei) {
  return {N, h, ei};
}

Back to top page