33.范围统计

发表于 2025-05-23 更新于 2025-06-04 分类于 ACM ， ACMCOURSE

范围统计

树状数组、线段树、KD树。

基本的区间统计问题

区间查询

给定 \(n\) 个数以及 \(m\) 组 \(a, b\)（其中 \(a>0\) 且 \(b>0\)），我们需要计算序号在区间 \([a,b]\) 的数值的和 \(sum(a,b)\)。例如，\(sum(1,1)=15\)，\(sum(5,8)=36\)。

为了解决这个问题，我们可以使用前缀和的方法。定义 \(pre(a)=sum(1,a)\)，那么 \(sum(a,b)=pre(b)-pre(a-1)\)。例如，\(sum(5,8)=pre(8)-pre(4)=95-59=36\)。

1	for(int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + c[i];

单点修改+区间查询

给定 \(n\) 个数以及 \(m\) 组操作，每组操作是以下两种之一：

操作1：\(1,x,a\)，将序号为 \(x\) 位置的数值加 \(a\)
操作2：\(2,a,b\)，求序号在区间 \([a,b]\) 的数值的和 \(sum(a,b)\)

例如，输入 \(1,6,9; 2,5,8\)，输出 \(18+10+8+9=45\)。

树状数组

前缀和方法存在以下不足：

每个序号“管理”整个前缀，涉及“下属”过多
每个序号被后续序号“管理”，更新要“汇报”的“上级”过多

改进思路是减少每个序号的“下级”与“上级”。我们采用以2的幂为单位的分级“管辖”方案：

“管辖”方案：以2的幂为单位分级：

“一级”：1,2归2管，3,4归4管，5,6归6管，7,8归8管……
“二级”：4要额外管理1_{2，所以2是4的直接下级，4是1}4的前缀和
“三级”：8要额外管理1_4、56，所以4、6也是8的直接下级
……

树状数组实际上是在数组中存储了一棵树的逻辑结构：

快速寻找直接“上级”的方法：

5(101)的上级是6(110)
4(100)的上级是8(1000)
6(110)的上级是8(1000)

规律是：最低的为“1”的二进制位+1。

求 \(x\) 的最低的为“1”的二进制位 \(lowbit\)：

1	int Lowbit(int x) {return x & -x;}

求 \(x\) 的上级：

1	x + Lowbit(int x)

求前缀和：找左侧最大组长

6(110)的左侧是4(100)——4<6且是最大组长
7(111)的左侧是6(110)——6<7且是最大组长

这些区间互不相交，且无遗漏，相加可得前缀和。规律是：最低的为“1”的二进制位−1。

求 \(x\) 的左侧最大组长：

1	x - Lowbit(int x)

单点修改时，需要逐层告知上级“辖区”内数值变化量：

void Update(int x, int v) {
    for(; x < maxn; x += Lowbit(x))
        a[x] += v;
}

前缀和查询时，需要逐个向左侧找最大组长，累加：

LL Query(int x) {
    LL res = 0;
    for(; x; x -= Lowbit(x))
        res += a[x];
    return res;
}

完整代码参考

#include<cstdio>
#include<cstdlib>
#include<cstring>
typedef long long LL;
const int maxn = 1e6 + 10;
int op, n, q;
LL a[maxn];
int Lowbit(int x) {return x & -x;}
void Update(int x, int v) {
    for(; x < maxn; x += Lowbit(x))
        a[x] += v;
}
LL Query(int x) {
    LL res = 0;
    for(; x; x -= Lowbit(x))
        res += a[x];
    return res;
}

int main() {
    int x, y;
    while(scanf("%d%d", &n, &q) != EOF) {
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &x);
            Update(i, x);
        }
        while(q --) {
            scanf("%d%d%d", &op, &x, &y);
            if(op == 1) {
                Update(x, y);
            }
            else {
                printf("%lld\n", Query(y) - Query(x - 1));
            }
        }
    }
    return 0;
}

扩展：

区间最值查询：树状数组无法直接维护区间最值，需结合其他数据结构（如线段树）
区间统计：支持维护区间特定统计信息（如奇偶性、模余等），需预处理辅助数组
区间合并/分裂：树状数组无法直接处理区间合并、分裂操作
区间覆盖：树状数组难以高效实现区间赋值或覆盖操作（需结合懒标记等技巧）

基于差分的扩展应用：

区间修改+单点查询：使用差分数组可高效支持，单点查询转化为前缀和计算
区间修改+区间查询：通过二阶差分与扩展BIT结构，可实现区间和查询
区间最值修改：树状数组不适合直接支持此类操作，需借助其他结构

高级扩展结构：

二维树状数组：支持二维平面的单点修改与矩形和查询
可持久化树状数组：支持历史版本查询，适用于函数式编程或离线算法
动态开点树状数组：用于高维稀疏数据，节省内存空间
树状数组套权值树：解决带权第k大等复杂统计问题
离线处理：结合莫队算法等，优化多次查询的处理效率

线段树

在数组之上再建一棵树

与树状数组不同，在线段树中，上级节点并不存在于数组中，而是另外建立的节点。这种结构使得我们可以更灵活地处理区间操作。

为了便于计算，我们使用左闭右开区间，数组序号从0开始。设根节点覆盖区间为 \([0,n)\)，则左子树为 \([0,\lfloor n/2 \rfloor)\)，右子树为 \([\lfloor n/2 \rfloor,n)\)。可以通过递归操作建树：

LL BuildSegTree(int now, int ls, int rs) {
    // now: 当前节点； [ls, rs) 左闭右开区间端点
    if(ls >= rs) return 0;
    if(ls == rs - 1) {return sum[now] = a[ls];}
    sum[now] = 0;
    int mid = ls + rs >> 1;
    sum[now] += BuildSegTree(now << 1, ls, mid);
    sum[now] += BuildSegTree(now << 1 | 1, mid, rs);
    return sum[now];
}

单点修改+区间查询

所有包含序号 \(x\) 的区间（节点）都要修改

void Update(int now, int ls, int rs, int x, int v) {
    if(ls >= rs) return;
    if(ls == rs - 1) {sum[now] += v; return;}
    int mid = ls + rs >> 1;
    if(x < mid) Update(now << 1, ls, mid, x, v);
    else Update(now << 1 | 1, mid, rs, x, v);
    sum[now] += v;
}

情况1：\([x,y)\)包含了 \(now\) 负责的 \([ls,rs)\) 区间，则 \(now\) 区间都计入

1	if(x <= ls && y >= rs) return sum[now];

情况2：部分重叠，\(y\) 在 \(mid\) 之右，表示 \(now\) 的右半部分需要考虑 \(x\) 在 \(mid\) 之左同理

1	if(y > mid) ret += Query(now << 1 \| 1, mid, rs, x, y);

只对与 \([x,y)\) 有交集的区间（子树）进行递归 \([x,y)\) 覆盖整个区间（子树）时，不再递归直接返回

LL Query(int now, int ls, int rs, int x, int y) {
    if(ls >= rs) return 0;
    if(x <= ls && y >= rs) return sum[now];
    int mid = ls + rs >> 1;
    LL ret = 0;
    if(x < mid) ret += Query(now << 1, ls, mid, x, y);
    if(y > mid) ret += Query(now << 1 | 1, mid, rs, x, y);
    return ret;
}

参考代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
typedef long long LL;
const int maxn = 1e6 + 10;
int a[maxn];
LL sum[maxn * 4];
LL BuildSegTree(int now, int ls, int rs) {
    // now: 当前节点； [ls, rs) 左闭右开区间端点
    if(ls >= rs) return 0;
    if(ls == rs - 1) {return sum[now] = a[ls];}
    sum[now] = 0;
    int mid = ls + rs >> 1;
    sum[now] += BuildSegTree(now << 1, ls, mid);
    sum[now] += BuildSegTree(now << 1 | 1, mid, rs);
    return sum[now];
}
void Update(int now, int ls, int rs, int x, int v) {
    if(ls >= rs) return;
    if(ls == rs - 1) {sum[now] += v; return;}
    int mid = ls + rs >> 1;
    if(x < mid) Update(now << 1, ls, mid, x, v);
    else Update(now << 1 | 1, mid, rs, x, v);
    sum[now] += v;
}
LL Query(int now, int ls, int rs, int x, int y) {
    if(ls >= rs) return 0;
    if(x <= ls && y >= rs) return sum[now];
    int mid = ls + rs >> 1;
    LL ret = 0;
    if(x < mid) ret += Query(now << 1, ls, mid, x, y);
    if(y > mid) ret += Query(now << 1 | 1, mid, rs, x, y);
    return ret;
}
int main() {
    int op, x, y, n, q;
    while(scanf("%d%d", &n, &q) != EOF) {
        for(int i = 0; i < n; i ++)
            scanf("%d", &a[i]);
        BuildSegTree(1, 0, n);
        while(q --) {
            scanf("%d%d%d", &op, &x, &y);
            if(op == 1) Update(1, 0, n, x - 1, y);
            else {
                printf("%lld\n", Query(1, 0, n, x - 1, y));
            }
        }
    }
    return 0;
}

区间修改

思考1：当修改区间包含 \(now\) 区间时，\(now\) 区间是否还需要递归

思考2：如果思考1中答案是"不递归，修改节点的值返回即可"

那新的查询区间在 \(now\) 内部（子树）怎么办？

懒标记（\(lazy\)）：修改时打标记，查询时标记只往下传 1 层修改时：

修改前与查询时：

懒标记下传参考代码

void UpdateNode(int now, int ls, int rs, LL v) {
    int rangeN = rs - ls;                           // 求区间长度
    sum[now] += rangeN * v;                         // 用下传的懒标记更新本区间和
    lasy[now] += v;                                 // 更新节点懒标记
}
void PushDown(int now, int ls, int rs) {
    if(lasy[now] == 0 || ls >= rs) return;          // 没有懒标记，或已到叶子
    int mid = ls + rs >> 1;
    UpdateNode(now << 1, ls, mid, lasy[now]);       // 下传懒标记到子节点
    UpdateNode(now << 1 | 1, mid, rs, lasy[now]);
    lasy[now] = 0;                                  // 清除本节点懒标记
}

带懒标记的区间更新操作

void PushUp(int now) {
    sum[now] = sum[now << 1] + sum[now << 1 | 1];
}
void Update(int now, int ls, int rs, int x, int y, int v) {
    if(ls >= rs) return;
    if(x <= ls && y >= rs) UpdateNode(now, ls, rs, v);
    else {
        PushDown(now, ls, rs);
        int mid = ls + rs >> 1;
        if(x < mid) Update(now << 1, ls, mid, x, y, v);
        if(y > mid) Update(now << 1 | 1, mid, rs, x, y, v);
        PushUp(now);
    }
}

带懒标记的区间查询

LL Query(int now, int ls, int rs, int x, int y) {
    if(ls >= rs) return 0;
    if(x <= ls && y >= rs) return sum[now];
    PushDown(now, ls, rs);
    int mid = ls + rs >> 1;
    LL ret = 0;
    if(x < mid) ret += Query(now << 1, ls, mid, x, y);
    if(y > mid) ret += Query(now << 1 | 1, mid, rs, x, y);
    return ret;
}

不只是求和：

区间最值查询：维护区间最大值/最小值，适用于RMQ（Range Maximum/Minimum Query）问题。
区间统计：维护区间内满足特定条件的元素个数，如区间奇偶性、模余性质等。
区间合并：处理区间合并、分裂等操作（如区间染色问题），常用于线段树合并或Segment Tree Beats。
区间覆盖：处理区间赋值、区间覆盖等操作，需使用懒标记进行高效更新。
区间翻转：处理区间反转操作，通常结合块状链表或平衡树结构实现。

区间操作：

区间修改+单点查询：使用懒标记优化（如区间加后单点查询），适合延迟传播机制。
区间修改+区间查询：结合懒标记和区间更新（如区间求和与区间加），是线段树基础应用之一。
区间最值更新：维护区间最值的同时支持取min/max等操作（如区间取max），常见于吉司机线段树（Segment Tree Beats）。
标记永久化：处理不可叠加操作的懒标记技巧（如区间覆盖不下传标记），适用于某些强制覆盖型操作。

更复杂的情况：

可持久化线段树：支持历史版本查询（如版本回退），适用于离线处理和函数式编程。
动态开点线段树：处理稀疏数据（无需预先开辟全部节点），节省空间适用于大范围但修改少的数据。
李超线段树：处理线段/直线覆盖的最值问题，适用于动态插入线段并查询区间最大/最小值。
线段树分治：结合时间线处理动态问题的离线方法，常用于解决带删除/回滚的问题。
权值线段树：维护值域分布的统计信息（如第k大查询），常配合离散化使用。
树链剖分套线段树：处理树上路径/子树操作，能高效应对树形结构上的区间操作。
平衡树套线段树：处理动态区间插入删除后的区间查询，如Treap/AVL嵌套线段树。
线段树套分块：结合两者优势处理大规模混合操作，提升部分操作效率。
二维线段树：处理矩阵的区间更新与查询，适用于二维平面上的操作。
线段树套Trie：处理数位相关的区间异或/最值问题，如可持久化01-Trie嵌套在线段树中。
区间连通性线段树：结合并查集思想处理区间连通性问题，适用于区间图论相关问题。

K-D树

思考：如果用线段树的写法统计二维的数据，直观的思路是什么？

void Update(int now, int v, int left, int right, int up, int down, int x, int y) {
    if(left == right || up == down)
        return;
    val[now] += v;
    if(left == right - 1 && up == down - 1)
        return;
    int lrmid = left + right >> 1;
    int udmid = up + down >> 1;
    if(x < lrmid && y < udmid) InitNode(0, now), Update(dr[0][now], v, left, lrmid, up, udmid, x, y);
    if(x < lrmid && y >= udmid) InitNode(1, now), Update(dr[1][now], v, left, lrmid, udmid, down, x, y);
    if(x >= lrmid && y < udmid) InitNode(2, now), Update(dr[2][now], v, lrmid, right, up, udmid, x, y);
    if(x >= lrmid && y >= udmid) InitNode(3, now), Update(dr[3][now], v, lrmid, right, udmid, down, x, y);
}

那三维、四维...K维的情况呢？

需要一个数据结构，处理任意维度的统计 \(K\) 个维度——\(K-Dimensional\)——K-D树

以二叉树的形式处理任意维度的数据

二维平面点个数统计

尝试建树：每次用一条线把平面递归地分为两部分，水平划分有用吗？当求一个矩形区域的点个数的时候

水平与竖直结合

思考：什么时候水平分，什么时候竖直分？

点的离散程度——坐标方差 \(x\) 坐标与 \(y\) 坐标哪个方差大，按哪个维度划分，让划分后的区域内，点尽可能的"聚集"，便于统计

统计思想：和线段树类似，覆盖区域则直接返回，否则递归

高维处理：同二维一样，各维度方差选最大的做划分

更多任务：

K近点
最远点
曼哈顿最近距离
……

参考模板：icpc_solution/DataStructure.md at master · CSGrandeur/icpc_solution · GitHub

例：k远点

平面上有 \(n\) 个点。现在有 \(m\) 次询问，每次给定一个点 \((px,py)\) 和一个整数 \(k\)，输出 \(n\) 个点中离 \((px,py)\) 的距离第 \(k\) 大的点的标号。如果有两个(或多个)点距离 \((px,py)\) 相同，那么认为标号较小的点距离较大。

\(1 \leq k \leq 20\)

分析：

第 \(k\) 远的点，就是从远到近的第 \(k\) 个，\(k\)范围不大。
KD树中每个节点都是一个具体的点，这个点的两个子树对应从它劈开（或横或竖）后的两个矩形区域
开一个小根堆（优先队列），并开始对树回溯（搜索）
每访问一个点，将其与堆顶比较，大就进堆，且保持堆里不超过 k 个元素
对于左右子树，优先访问子树的矩形距离目标点更远的那个
如果堆里有k个元素，此时一棵子树的矩形距离比堆顶还近，那这课子树不用搜（分支限界/剪枝）

发散：k近点问题思路类似

例：平面统计

多次操作，对整数坐标位置加数字或者求某个矩形区域的数字和

每个节点对应一个矩形区域
这个矩形区域被它横或竖分成两半
该节点“掌管”一棵子树

在节点维护子树元素个数，某个坐标增加数值，就是节点的插入或更新

统计操作类似线段树——全覆盖（要统计的矩形覆盖了子树的矩形）就子树的统计值返回，部分覆盖就递归进入子树。

思考：KD树的平衡问题。必要时可以通过平衡因子判断后对整棵子树离线重构。重构而不是像平衡树那样旋转是因为KD树没法那样旋转……