data-structure/divide-interval.hpp

• View this file on GitHub
• Last update: 2023-05-26 23:34:57+09:00
• Include: #include "data-structure/divide-interval.hpp"

Verified with

• verify/verify-aoj-other/aoj-3506.test.cpp
• verify/verify-yuki/yuki-1170-divide-interval.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>
using namespace std;

// セグ木状に区間を分割したときの処理
//
// 2*B 個の頂点を持つグラフを考える
// B+i が元のグラフの頂点 i に対応する
struct DivideInterval {
  int N, B;
  DivideInterval(int n) : N(n), B(1) {
    while (B < N) B *= 2;
  }
  // 初期化

  // O(N) 根から葉方向へ push する
  // f(p, c) : p -> c へ伝播
  template <typename F>
  void push(const F& f) {
    for (int p = 1; p < B; p++) {
      f(p, p * 2 + 0);
      f(p, p * 2 + 1);
    }
  }
  // O(N) 葉から根の方向に update する
  // f(p, c1, c2) : c1 と c2 の結果を p へマージ
  template <typename F>
  void update(const F& f) {
    for (int p = B - 1; p > 0; p--) {
      f(p, p * 2 + 0, p * 2 + 1);
    }
  }

  // [l, r) に対応する index の列を返す
  // 順番は左から右へ並んでいる
  // 例: [1, 11) : [1, 2), [2, 4), [4, 8), [8, 10), [10, 11)
  vector<int> range(int l, int r) {
    assert(0 <= l and l <= r and r <= N);
    vector<int> L, R;
    for (l += B, r += B; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L.push_back(l), l++;
      if (r & 1) r--, R.push_back(r);
    }
    for (int i = (int)R.size() - 1; i >= 0; i--) L.push_back(R[i]);
    return L;
  }
  // [l, r) に対応する index に対してクエリを投げる(区間は昇順)
  // f(i) : 区間 i にクエリを投げる
  template <typename F>
  void apply(int l, int r, const F& f) {
    assert(0 <= l and l <= r and r <= N);
    for (int i : range(l, r)) f(i);
  }
};

#line 2 "data-structure/divide-interval.hpp"

#include <cassert>
#include <vector>
using namespace std;

// セグ木状に区間を分割したときの処理
//
// 2*B 個の頂点を持つグラフを考える
// B+i が元のグラフの頂点 i に対応する
struct DivideInterval {
  int N, B;
  DivideInterval(int n) : N(n), B(1) {
    while (B < N) B *= 2;
  }
  // 初期化

  // O(N) 根から葉方向へ push する
  // f(p, c) : p -> c へ伝播
  template <typename F>
  void push(const F& f) {
    for (int p = 1; p < B; p++) {
      f(p, p * 2 + 0);
      f(p, p * 2 + 1);
    }
  }
  // O(N) 葉から根の方向に update する
  // f(p, c1, c2) : c1 と c2 の結果を p へマージ
  template <typename F>
  void update(const F& f) {
    for (int p = B - 1; p > 0; p--) {
      f(p, p * 2 + 0, p * 2 + 1);
    }
  }

  // [l, r) に対応する index の列を返す
  // 順番は左から右へ並んでいる
  // 例: [1, 11) : [1, 2), [2, 4), [4, 8), [8, 10), [10, 11)
  vector<int> range(int l, int r) {
    assert(0 <= l and l <= r and r <= N);
    vector<int> L, R;
    for (l += B, r += B; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L.push_back(l), l++;
      if (r & 1) r--, R.push_back(r);
    }
    for (int i = (int)R.size() - 1; i >= 0; i--) L.push_back(R[i]);
    return L;
  }
  // [l, r) に対応する index に対してクエリを投げる(区間は昇順)
  // f(i) : 区間 i にクエリを投げる
  template <typename F>
  void apply(int l, int r, const F& f) {
    assert(0 <= l and l <= r and r <= N);
    for (int i : range(l, r)) f(i);
  }
};

Back to top page