跳转至

整体二分⚓︎

整体二分（\text{Parallel Binary Search}）是一种用于处理离线查询的分治算法，常用于答案具有单调性的离线查询问题，即查询答案随某个参数（如时间、权值、操作次数）单调变化的情况。

区间查询⚓︎

整体二分的基本思想是将所有查询的答案范围进行二分，然后在每次二分中，批量处理所有查询，判断哪些查询在当前中点满足条件，从而缩小查询的答案范围。在二分的中点 mid，暂时假设所有操作 \leq mid 已生效，然后判断哪些查询已经满足条件。

整体二分的步骤：

  1. 初始化每个查询的答案范围为 [L, R]，通常为问题中可能的最小值和最大值。
  2. 重复以下步骤，直到所有查询的答案范围收敛：
    1. 对于每个查询，计算当前中点 mid = (L + R) / 2。
    2. 将所有查询按照 mid 分组。
    3. 对于每个 mid，模拟执行所有操作 \le mid。
    4. 对于每个查询，检查当前状态是否满足查询条件；若满足，则更新答案范围为 [L, mid]，否则更新为 [mid + 1, R]。
  3. 最终每个查询的答案即为其收敛后的 L。

与线段树分治的区别

线段树分治是将时间维度引入线段树结构中，处理动态修改和查询的问题。而整体二分则是通过对查询答案范围进行二分来批量处理离线查询问题。两者都是分治思想的应用，但侧重点不同。

【模板】可持久化线段树 2

给定 n 个整数构成的序列，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值

时间复杂度

O((n+q) \log^{2} n)，其中 n 为序列长度，q 为查询次数。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct BIT {
  explicit BIT(int64_t n) : n(n), tree(n + 1) {}

  void point_add(int64_t x, int64_t delta) {
    for (; x <= n; x += lowbit(x)) { tree[x] += delta; }
  }

  int64_t sum(int64_t x) {
    int64_t ret = 0;
    for (; x > 0; x -= lowbit(x)) { ret += tree[x]; }
    return ret;
  }

  int64_t range_sum(int64_t x, int64_t y) { return sum(y) - sum(x - 1); }

  static int64_t lowbit(int64_t x) { return x & (-x); }

  int64_t n;
  vector<int64_t> tree;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;

  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  vector<int64_t> indexs(n + 1);
  iota(indexs.begin(), indexs.end(), 0);
  sort(indexs.begin() + 1, indexs.end(), [&](int64_t a, int64_t b) { return nums[a] < nums[b]; });

  struct query {
    int64_t l, r, k;
  };

  vector<query> queries(m + 1);
  for (int64_t i = 1; i <= m; i++) { cin >> queries[i].l >> queries[i].r >> queries[i].k; }
  vector<int64_t> qid(m + 1);
  iota(qid.begin(), qid.end(), 0);

  vector<int64_t> left(m + 1);
  vector<int64_t> right(m + 1);

  BIT bit(n);

  vector<int64_t> answers(m + 1);

  auto dfs = [&](auto &&self, int64_t ql, int64_t qr, int64_t l, int64_t r) -> void {
    if (ql > qr) { return; }  // 无查询
    if (l == r) {
      for (int64_t i = ql; i <= qr; i++) { answers[qid[i]] = nums[indexs[l]]; }
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    // 更新BIT, 将小于等于mid的元素加入BIT
    for (int64_t i = l; i <= mid; i++) { bit.point_add(indexs[i], 1); }
    // 分配查询
    int64_t left_count = 0, right_count = 0;
    for (int64_t i = ql; i <= qr; i++) {
      int64_t cnt = bit.range_sum(queries[qid[i]].l, queries[qid[i]].r);
      if (queries[qid[i]].k <= cnt) {  // 在左半区间
        left[left_count++] = qid[i];
      } else {  // 在右半区间, 更新k值
        queries[qid[i]].k    -= cnt;
        right[right_count++]  = qid[i];
      }
    }
    // 恢复BIT
    for (int64_t i = l; i <= mid; i++) { bit.point_add(indexs[i], -1); }
    // 重新排列qid
    for (int64_t i = 0; i < left_count; i++) { qid[ql + i] = left[i]; }
    for (int64_t i = 0; i < right_count; i++) { qid[ql + i + left_count] = right[i]; }
    // 递归处理左右子区间
    self(self, ql, ql + left_count - 1, l, mid);
    self(self, ql + left_count, qr, mid + 1, r);
  };

  dfs(dfs, 1, m, 1, n);
  for (int64_t i = 1; i <= m; i++) { cout << answers[i] << "\n"; }
  return 0;
}

分治中心维护

通过维护全局指针来避免重复计算，将树状数组的多次清空重建改为单次顺序更新。这种方法不需要对询问做出修改。

时间复杂度仍为 O((n+q) \log^{2} n)，但常数项更小。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct BIT {
  explicit BIT(int64_t n) : n(n), tree(n + 1) {}

  void point_add(int64_t x, int64_t delta) {
    for (; x <= n; x += lowbit(x)) { tree[x] += delta; }
  }

  int64_t sum(int64_t x) {
    int64_t ret = 0;
    for (; x > 0; x -= lowbit(x)) { ret += tree[x]; }
    return ret;
  }

  int64_t range_sum(int64_t x, int64_t y) { return sum(y) - sum(x - 1); }

  static int64_t lowbit(int64_t x) { return x & (-x); }

  int64_t n;
  vector<int64_t> tree;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;

  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  vector<int64_t> indexs(n + 1);
  iota(indexs.begin(), indexs.end(), 0);
  sort(indexs.begin() + 1, indexs.end(), [&](int64_t a, int64_t b) { return nums[a] < nums[b]; });

  struct query {
    int64_t l, r, k;
  };

  vector<query> queries(m + 1);
  for (int64_t i = 1; i <= m; i++) { cin >> queries[i].l >> queries[i].r >> queries[i].k; }
  vector<int64_t> qid(m + 1);
  iota(qid.begin(), qid.end(), 0);

  vector<int64_t> left(m + 1);
  vector<int64_t> right(m + 1);

  BIT bit(n);
  int64_t used = 0;  // 记录已经加入BIT的元素数量

  vector<int64_t> answers(m + 1);

  auto dfs = [&](auto &&self, int64_t ql, int64_t qr, int64_t l, int64_t r) -> void {
    if (ql > qr) { return; }  // 无查询
    if (l == r) {
      for (int64_t i = ql; i <= qr; i++) { answers[qid[i]] = nums[indexs[l]]; }
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    while (used < mid) {  // 更新分治中心, 数据不足就继续加入
      used++;
      bit.point_add(indexs[used], 1);
    }
    while (used > mid) {  // 恢复分治中心, 数据过多就移除
      bit.point_add(indexs[used], -1);
      used--;
    }
    // 分配查询
    int64_t left_count = 0, right_count = 0;
    for (int64_t i = ql; i <= qr; i++) {
      int64_t cnt = bit.range_sum(queries[qid[i]].l, queries[qid[i]].r);
      if (queries[qid[i]].k <= cnt) {  // 在左半区间
        left[left_count++] = qid[i];
      } else {  // 在右半区间, 无需更新k值
        right[right_count++] = qid[i];
      }
    }
    // 重新排列qid
    for (int64_t i = 0; i < left_count; i++) { qid[ql + i] = left[i]; }
    for (int64_t i = 0; i < right_count; i++) { qid[ql + i + left_count] = right[i]; }
    // 递归处理左右子区间
    self(self, ql, ql + left_count - 1, l, mid);
    self(self, ql + left_count, qr, mid + 1, r);
  };

  dfs(dfs, 1, m, 1, n);
  for (int64_t i = 1; i <= m; i++) { cout << answers[i] << "\n"; }
  return 0;
}

带修改的区间查询⚓︎

修改操作会影响查询结果时，可以将修改操作和查询操作一起离线处理，每次修改操作可以视作将一个元素从旧值修改为新值的两次操作。

Dynamic Rankings
C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct BIT {
  explicit BIT(int64_t n) : n(n), tree(n + 1) {}

  void point_add(int64_t x, int64_t delta) {
    for (; x <= n; x += lowbit(x)) { tree[x] += delta; }
  }

  int64_t sum(int64_t x) {
    int64_t ret = 0;
    for (; x > 0; x -= lowbit(x)) { ret += tree[x]; }
    return ret;
  }

  int64_t range_sum(int64_t x, int64_t y) { return sum(y) - sum(x - 1); }

  static int64_t lowbit(int64_t x) { return x & (-x); }

  int64_t n;
  vector<int64_t> tree;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;

  // 修改操作: x 为位置, y = 1表示添加, -1表示删除, op = 0, v 为值
  // 查询操作: x 为左端点, y 为右端点, op = 1, v 为查询的第k小值, id 为查询编号
  struct Query {
    int64_t x, y, op, v, id;
  };

  int64_t max_value = 0;
  vector<int64_t> nums(n + 1);
  // 最多 n 个初始值, m 次修改(每次修改视作删除旧值和添加新值两次操作)
  vector<Query> queries(n + 2 * m + 1);
  int64_t op_id = 0, query_id = 0;
  for (int64_t i = 1; i <= n; ++i) {
    cin >> nums[i];
    queries[++op_id] = {.x = i, .y = 1, .op = 0, .v = nums[i], .id = 0};
    max_value        = max(max_value, nums[i]);
  }
  char type;
  for (int64_t i = 1; i <= m; ++i) {
    cin >> type;
    if (type == 'Q') {
      int64_t l, r, k;
      cin >> l >> r >> k;
      queries[++op_id] = {.x = l, .y = r, .op = 1, .v = k, .id = ++query_id};
    } else {
      int64_t pos, v;
      cin >> pos >> v;
      queries[++op_id] = {.x = pos, .y = -1, .op = 0, .v = nums[pos], .id = 0};  // 删除旧值
      queries[++op_id] = {.x = pos, .y = 1, .op = 0, .v = v, .id = 0};           // 添加新值
      nums[pos]        = v;
      max_value        = max(max_value, v);
    }
  }
  vector<int64_t> qid(op_id + 1);
  iota(qid.begin(), qid.end(), 0);

  vector<int64_t> left(op_id + 1);
  vector<int64_t> right(op_id + 1);

  vector<int64_t> answers(query_id + 1);

  BIT bit(n);

  auto dfs = [&](auto &&self, int64_t ql, int64_t qr, int64_t l, int64_t r) -> void {
    if (ql > qr) { return; }  // 无查询
    if (l == r) {
      for (int64_t i = ql; i <= qr; i++) {
        if (queries[qid[i]].op == 1) { answers[queries[qid[i]].id] = l; }
      }
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    // 分配查询
    int64_t left_count = 0, right_count = 0;
    for (int64_t i = ql; i <= qr; i++) {
      auto [x, y, op, v, id] = queries[qid[i]];
      if (op == 0) {  // 修改操作
        if (v <= mid) {
          bit.point_add(x, y);
          left[left_count++] = qid[i];
        } else {
          right[right_count++] = qid[i];
        }
      } else {  // 查询操作
        int64_t cnt = bit.range_sum(x, y);
        if (v <= cnt) {  // 在左半区间
          left[left_count++] = qid[i];
        } else {  // 在右半区间, 更新k值
          queries[qid[i]].v    -= cnt;
          right[right_count++]  = qid[i];
        }
      }
    }
    // 重新排列qid
    for (int64_t i = 0; i < left_count; i++) { qid[ql + i] = left[i]; }
    for (int64_t i = 0; i < right_count; i++) { qid[ql + i + left_count] = right[i]; }
    // 恢复BIT
    for (int64_t i = 0; i < left_count; i++) {
      auto [x, y, op, v, id] = queries[left[i]];
      if (op == 0 && v <= mid) { bit.point_add(x, -y); }
    }
    // 递归处理左右子区间
    self(self, ql, ql + left_count - 1, l, mid);
    self(self, ql + left_count, qr, mid + 1, r);
  };
  // 查询id从1到op_id, 答案范围从 0 到 max_value
  dfs(dfs, 1, op_id, 0, max_value);
  for (int64_t i = 1; i <= query_id; i++) { cout << answers[i] << "\n"; }

  return 0;
}

评论