题解 | #区间增量与区间小于计数#

在处理大规模数据集合的区间更新与非线性统计查询（如“小于特定值的元素计数”）时，传统的线段树（Segment Tree）或树状数组（Fenwick Tree）在处理简单的区间和、区间最值时表现优异，但在面对区间秩（Rank）查询且伴随区间增量更新时，其逻辑复杂度会显著增加。

一、 问题分析

1. 数据规模：，这意味着算法的时间复杂度上限应控制在 或 。
2. 动态更新：区间增量修改（）破坏了预处理有序集合的静态性质。
3. 多维统计：查询“小于 的个数”本质上是在寻找二维平面内的点集统计（下标维度与数值维度），但在区间动态更新的约束背景下，标准的高维数据结构（如持久化线段树）难以直接处理 Lazy 标记转换。

二、 分块动态秩维护 (Square Root Decomposition)

为了平衡区间更新的灵活性与区间查询的效率，采用分块（Square Root Decomposition）策略是该问题的最优解。

核心思想： 将原始数组划分为大小约为 的连续块。对于每个块，不仅维护其原始数据的局部状态，还维护一个有序副本。利用有序性，可以通过二分查找在对数时间内完成“小于计数”的统计。

三、 算法实现

算法实现过程：

1. 初始化

• 分块策略：将数组划分为 个块。
• 数据结构维护：
  • data[]：存储原始数组元素（随更新操作实时改变）。
  • sorted_data[]：每个块内部维护一个排好序的数组副本。
  • lazy_tag[]：记录每个块整体收到的增量偏移（Lazy Addition）。

2. 区间增量处理 (Range Update)

当执行操作 1 将 区间增加 时：

• 整块处理：对于完全包含在 之间的块，直接累加其 lazy_tag[block_id] += x。该操作复杂度为 。
• 散块处理：对于区间两端的非完整块：
  1. 直接在 data[] 数组中对对应元素进行修改。
  2. 块内重构：为了保持 sorted_data[] 的有序性，需要对受影响的块进行重新排序。
     • 优化策略：不需要重新调用 的排序算法。由于原序列是有序的且增量是统一的，可以提取出被修改元素和未修改元素，通过线性归并 (Merge Sort Loop) 在 时间内恢复有序性。

3. 区间秩查询处理 (Range Query)

当执行操作 2 查询 中小于 的元素个数时：

• 整块计数：对于完全包含在 之间的块，目标是统计 ，即 。
  • 在 sorted_data[] 中使用 std::lower_bound（二分查找）检索第一个大于等于 的位置。
  • 该块的贡献即为二分所得的索引偏移量。
• 散块计数：对于区间两端的非完整块，直接遍历 data[] 对应元素，判断其 data[i] + lazy_tag 是否小于 。
• 统计合并：累加所有块的贡献值并输出。

四、 复杂度分析与考量

维度	复杂度	说明
预处理		初始分块排序。
区间更新 (Update)		包括 个块的标签更新及 2 个散块的线性重构。
区间查询 (Query)		包含至多 次块内二分检索及少量散块遍历。
空间复杂度		维护原始数组、排序副本及分块辅助信息。

为什么不选择树状结构？ 虽然线段树套平衡树（或线段树套动态标号）可以将复杂度优化至 ，但其常数巨大且实现逻辑极其复杂（涉及大量节点的动态申请与平衡旋转）。分块算法在 的量级下，凭借极小的常数因子和优秀的缓存局部性，通常能在线限内稳定运行，且架构更易于调试。

五、 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Block {
    int l, r;
    ll lazy;
    vector<ll> sorted;
};

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

    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int B = max(1, (int)sqrt(n));
    int num_blocks = (n + B - 1) / B;
    vector<Block> blocks(num_blocks);

    for (int i = 0; i < n; i++) {
        int bid = i / B;
        if (blocks[bid].sorted.empty()) {
            blocks[bid].l = i;
            blocks[bid].lazy = 0;
        }
        blocks[bid].r = i;
        blocks[bid].sorted.push_back(a[i]);
    }

    for (int bid = 0; bid < num_blocks; bid++) {
        sort(blocks[bid].sorted.begin(), blocks[bid].sorted.end());
    }

    auto rebuild = [&](int bid) {
        blocks[bid].sorted.clear();
        for (int i = blocks[bid].l; i <= blocks[bid].r; i++) {
            blocks[bid].sorted.push_back(a[i]);
        }
        sort(blocks[bid].sorted.begin(), blocks[bid].sorted.end());
    };

    while (q--) {
        int op;
        cin >> op;
        int l, r;
        ll x;
        cin >> l >> r >> x;
        l--;
        r--;

        int bL = l / B;
        int bR = r / B;

        if (op == 1) {
            if (bL == bR) {
                for (int i = l; i <= r; i++)
                    a[i] += x;
                rebuild(bL);
            } else {
                for (int i = l; i <= blocks[bL].r; i++)
                    a[i] += x;
                rebuild(bL);

                for (int i = blocks[bR].l; i <= r; i++)
                    a[i] += x;
                rebuild(bR);

                for (int bid = bL + 1; bid < bR; bid++) {
                    blocks[bid].lazy += x;
                }
            }
        } else if (op == 2) {
            int ans = 0;

            if (bL == bR) {
                for (int i = l; i <= r; i++) {
                    if (a[i] + blocks[bL].lazy < x)
                        ans++;
                }
            } else {
                for (int i = l; i <= blocks[bL].r; i++) {
                    if (a[i] + blocks[bL].lazy < x)
                        ans++;
                }

                for (int i = blocks[bR].l; i <= r; i++) {
                    if (a[i] + blocks[bR].lazy < x)
                        ans++;
                }

                for (int bid = bL + 1; bid < bR; bid++) {
                    ll target = x - blocks[bid].lazy;
                    auto it = lower_bound(blocks[bid].sorted.begin(), blocks[bid].sorted.end(),
                                          target);
                    ans += distance(blocks[bid].sorted.begin(), it);
                }
            }

            cout << ans << "\n";
        }
    }
}