ds/segtree/dual_segtree.hpp

• View this file on GitHub
• Last update: 2022-12-04 02:25:39+09:00
• Include: #include "ds/segtree/dual_segtree.hpp"

Required by

• geo/range_closest_pair_query.hpp
• graph/ds/dual_tree_monoid.hpp
• graph/minimum_spanning_tree.hpp

Verified with

• test/aoj/DSL_2_D.test.cpp
• test/aoj/GRL_2_A.test.cpp
• test/library_checker/datastructure/range_affine_point_add.test.cpp
• test/library_checker/tree/mst.test.cpp
• test/mytest/range_closest_pair.test.cpp
• test/yukicoder/1524.test.cpp
• test/yukicoder/2498.test.cpp
• test/yukicoder/913.test.cpp
• test_atcoder/abc270_f.test.cpp
• test_atcoder/abc301h.test.cpp

Code

#pragma once

template <typename Monoid>
struct Dual_SegTree {
  using MA = Monoid;
  using A = typename MA::value_type;
  int n, log, size;
  vc<A> laz;

  Dual_SegTree() : Dual_SegTree(0) {}
  Dual_SegTree(int n) { build(n); }

  void build(int m) {
    n = m;
    log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    laz.assign(size << 1, MA::unit());
  }

  A get(int p) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return laz[p];
  }

  vc<A> get_all() {
    FOR(i, size) push(i);
    return {laz.begin() + size, laz.begin() + size + n};
  }

  void apply(int l, int r, const A& a) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return;
    l += size, r += size;
    if (!MA::commute) {
      for (int i = log; i >= 1; i--) {
        if (((l >> i) << i) != l) push(l >> i);
        if (((r >> i) << i) != r) push((r - 1) >> i);
      }
    }
    while (l < r) {
      if (l & 1) all_apply(l++, a);
      if (r & 1) all_apply(--r, a);
      l >>= 1, r >>= 1;
    }
  }

private:
  void push(int k) {
    if (laz[k] == MA::unit()) return;
    all_apply(2 * k, laz[k]), all_apply(2 * k + 1, laz[k]);
    laz[k] = MA::unit();
  }
  void all_apply(int k, A a) { laz[k] = MA::op(laz[k], a); }
};

#line 2 "ds/segtree/dual_segtree.hpp"

template <typename Monoid>
struct Dual_SegTree {
  using MA = Monoid;
  using A = typename MA::value_type;
  int n, log, size;
  vc<A> laz;

  Dual_SegTree() : Dual_SegTree(0) {}
  Dual_SegTree(int n) { build(n); }

  void build(int m) {
    n = m;
    log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    laz.assign(size << 1, MA::unit());
  }

  A get(int p) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return laz[p];
  }

  vc<A> get_all() {
    FOR(i, size) push(i);
    return {laz.begin() + size, laz.begin() + size + n};
  }

  void apply(int l, int r, const A& a) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return;
    l += size, r += size;
    if (!MA::commute) {
      for (int i = log; i >= 1; i--) {
        if (((l >> i) << i) != l) push(l >> i);
        if (((r >> i) << i) != r) push((r - 1) >> i);
      }
    }
    while (l < r) {
      if (l & 1) all_apply(l++, a);
      if (r & 1) all_apply(--r, a);
      l >>= 1, r >>= 1;
    }
  }

private:
  void push(int k) {
    if (laz[k] == MA::unit()) return;
    all_apply(2 * k, laz[k]), all_apply(2 * k + 1, laz[k]);
    laz[k] = MA::unit();
  }
  void all_apply(int k, A a) { laz[k] = MA::op(laz[k], a); }
};

Back to top page