【题目描述】这是一道模板题。给出一个 n×m 的零矩阵 A你需要完成如下操作1xyk表示元素 Ax,y自增 k2abcd表示询问左上角为 (a,b)右下角为 (c,d) 的子矩阵内所有数的和。【输入】输入的第一行有两个正整数 n,m接下来若干行每行一个操作直到文件结束。【输出】对于每个 2 操作输出一个整数表示对于这个操作的回答。【输入样例】2 2 1 1 1 3 1 2 2 4 2 1 1 2 2【输出样例】7【提示】数据范围与提示对于 10% 的数据n1对于另 10% 的数据m1对于全部数据1≤n,m≤2^12,1≤x,a,c≤n,1≤y,b,d≤m,∣k∣≤10^5 保证操作数目不超过 3×10^5 且询问的子矩阵存在。一、 题目分析【题目大意】维护一个n×m的初始全为0的矩阵 A要求高效支持两种操作单点修改将矩阵中坐标为(x,y)的元素自增 k。子矩阵求和查询左上角为(a,b)右下角为 (c,d) 的子矩阵内所有元素的和。【数据范围与核心矛盾】1≤n,m≤4096操作总数 ≤3×10^5。 如果每次修改是 O(1)查询用两层for循环暴力遍历查询的时间复杂度将高达O(N×M)在 30 万次操作下绝对会超时。我们必须将单次操作的复杂度降到对数级别即O(logN×logM)。二、 思考过程一维到二维的推演 一维树状数组tree[x]维护的是一段长度为lowbit(x)的线状区间。因为二维平面的横纵坐标是绝对正交、互不干扰的所以当我们升维到二维时tree[x][y]维护的就是一个矩形面积宽度为lowbit(x)高度为lowbit(y)。修改操作单点波及面 当 (x,y) 发生改变时我们需要更新所有“管辖领地”包含 (x,y) 的大节点。在一维中是用for循环不断ilowbit(i)往后跳在二维中只需要将x轴的跳跃和y轴的跳跃进行双层嵌套组合即可。查询操作前缀矩阵和 同样利用双层嵌套x-lowbit(x)配合y-lowbit(y)我们可以极其高效地拼凑出从左上角 (1,1) 到右下角 (x,y) 的整个前缀矩阵的面积和。三、 解题思路树状数组原生的query(x,y)只能求出“紧贴左上角”的前缀矩阵和。但题目要求的是任意一个悬空的子矩阵 (a,b) 到 (c,d) 的和。这时候必须引入二维前缀和的核心——容斥原理 要计算悬空子矩阵的面积我们可以用大矩形挖去多余的部分先拿到大矩形query(c,d)。挖掉它上方多余的矩形-query(a-1,d)。挖掉它左边多余的矩形-query(c,b-1)。因为左上角的矩形被挖了两次必须补偿回来query(a-1,b-1)。最终公式Ansquery(c,d)-query(c,b-1)-query(a-1,d)query(a-1,b-1)。四、 算法设计数据结构二维数组c[5000][5000]。因为矩阵求和极易突破21亿的整型极限该数组及查询函数的返回值必须使用long long。lowbit函数x(-x)提取二进制最低位的1。add函数双层for循环控制变量均使用lowbit()向上攀升更新。query 函数双层for循环控制变量均使用-lowbit()向下聚拢求和。IO 优化使用ios::sync_with_stdio(false); cin.tie(0);应对 30 万次的庞大输入流。五、 时空复杂度分析时间复杂度单次add和query的时间复杂度均为O(logN×logM)。总时间复杂度为O(Q×logN×logM)在N4096时logN≈12。单次操作最多只需循环144 次。30 万次操作的计算量在千万级别1 秒内毫无压力。空间复杂度需要开辟一个5000×5000的64位整数数组空间复杂度O(N×M)约占用 200MB内存符合常规竞赛的空间限制。六、 易错点总结容斥边界切勿漏减1在容斥原理公式中必须是a-1和b-1。如果写成a和b会把子矩阵边界上的那一行/那一列也给错误地挖掉。全局变量与局部变量撞车我们以往的风格是将树状数组命名为c。而在处理询问时局部变量又定义了int a,b,c,d;。虽然C允许局部变量遮蔽全局变量使得query(c, d)传递的是局部变量但这在工程上是极度危险的做法。强烈建议将全局树状数组命名为cc避免 Bug。数据溢出二维求和极其庞大一定要将ans和cc数组开成long long。七、 题解本题是二维树状数组最纯粹的模板题。通过两层嵌套循环将一维的线段管辖扩展至二维的矩形管辖再辅以二维前缀和的容斥原理用极其轻量级的代码和极小的常数完美解决了二维动态矩阵的维护问题。相比于二维线段树树套树二维树状数组是考场上兼顾速度与代码稳定性的最优解。八、 完整代码#include iostream using namespace std; long long cc[5000][5000];//树状数组 int n,m; //返回x二进制表示下最低位1所代表的整数 int lowbit(int x){ return x(-x); } //树状数组更新操作 void add(int x,int y,int k){ //双层循环x轴和y轴均向上攀升更新所有包含(x,y)的大管辖矩阵 for(int ix;in;ilowbit(i)){ for(int jy;jm;jlowbit(j)){ cc[i][j]k; } } } //树状数组查询操作 //查询左上角为(1,1)右下角为(x,y)的前缀矩阵和 long long query(int x,int y){ long long ret0ll;//记录前缀和 //双层循环x轴和y轴均向下聚拢无缝拼凑出前缀面积 for(int ix;i0;i-lowbit(i)){ for(int jy;j0;j-lowbit(j)){ retcc[i][j]; } } return ret; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; int t; while(cint){ if(t1){//自增操作 int x,y,k; cinxyk; add(x,y,k); } else{//查询操作 int a,b,c,d; cinabcd; //套用二维前缀和容斥原理公式 //务必注意是a-1和b-1否则会多挖掉一行一列 coutquery(c,d)-query(c,b-1)-query(a-1,d)query(a-1,b-1)\n; } } }
打鼹鼠_二维树状数组（信息学奥赛一本通- P1540）（二维树状数组模版题）
【题目描述】这是一道模板题。给出一个 n×m 的零矩阵 A你需要完成如下操作1xyk表示元素 Ax,y自增 k2abcd表示询问左上角为 (a,b)右下角为 (c,d) 的子矩阵内所有数的和。【输入】输入的第一行有两个正整数 n,m接下来若干行每行一个操作直到文件结束。【输出】对于每个 2 操作输出一个整数表示对于这个操作的回答。【输入样例】2 2 1 1 1 3 1 2 2 4 2 1 1 2 2【输出样例】7【提示】数据范围与提示对于 10% 的数据n1对于另 10% 的数据m1对于全部数据1≤n,m≤2^12,1≤x,a,c≤n,1≤y,b,d≤m,∣k∣≤10^5 保证操作数目不超过 3×10^5 且询问的子矩阵存在。一、 题目分析【题目大意】维护一个n×m的初始全为0的矩阵 A要求高效支持两种操作单点修改将矩阵中坐标为(x,y)的元素自增 k。子矩阵求和查询左上角为(a,b)右下角为 (c,d) 的子矩阵内所有元素的和。【数据范围与核心矛盾】1≤n,m≤4096操作总数 ≤3×10^5。 如果每次修改是 O(1)查询用两层for循环暴力遍历查询的时间复杂度将高达O(N×M)在 30 万次操作下绝对会超时。我们必须将单次操作的复杂度降到对数级别即O(logN×logM)。二、 思考过程一维到二维的推演 一维树状数组tree[x]维护的是一段长度为lowbit(x)的线状区间。因为二维平面的横纵坐标是绝对正交、互不干扰的所以当我们升维到二维时tree[x][y]维护的就是一个矩形面积宽度为lowbit(x)高度为lowbit(y)。修改操作单点波及面 当 (x,y) 发生改变时我们需要更新所有“管辖领地”包含 (x,y) 的大节点。在一维中是用for循环不断ilowbit(i)往后跳在二维中只需要将x轴的跳跃和y轴的跳跃进行双层嵌套组合即可。查询操作前缀矩阵和 同样利用双层嵌套x-lowbit(x)配合y-lowbit(y)我们可以极其高效地拼凑出从左上角 (1,1) 到右下角 (x,y) 的整个前缀矩阵的面积和。三、 解题思路树状数组原生的query(x,y)只能求出“紧贴左上角”的前缀矩阵和。但题目要求的是任意一个悬空的子矩阵 (a,b) 到 (c,d) 的和。这时候必须引入二维前缀和的核心——容斥原理 要计算悬空子矩阵的面积我们可以用大矩形挖去多余的部分先拿到大矩形query(c,d)。挖掉它上方多余的矩形-query(a-1,d)。挖掉它左边多余的矩形-query(c,b-1)。因为左上角的矩形被挖了两次必须补偿回来query(a-1,b-1)。最终公式Ansquery(c,d)-query(c,b-1)-query(a-1,d)query(a-1,b-1)。四、 算法设计数据结构二维数组c[5000][5000]。因为矩阵求和极易突破21亿的整型极限该数组及查询函数的返回值必须使用long long。lowbit函数x(-x)提取二进制最低位的1。add函数双层for循环控制变量均使用lowbit()向上攀升更新。query 函数双层for循环控制变量均使用-lowbit()向下聚拢求和。IO 优化使用ios::sync_with_stdio(false); cin.tie(0);应对 30 万次的庞大输入流。五、 时空复杂度分析时间复杂度单次add和query的时间复杂度均为O(logN×logM)。总时间复杂度为O(Q×logN×logM)在N4096时logN≈12。单次操作最多只需循环144 次。30 万次操作的计算量在千万级别1 秒内毫无压力。空间复杂度需要开辟一个5000×5000的64位整数数组空间复杂度O(N×M)约占用 200MB内存符合常规竞赛的空间限制。六、 易错点总结容斥边界切勿漏减1在容斥原理公式中必须是a-1和b-1。如果写成a和b会把子矩阵边界上的那一行/那一列也给错误地挖掉。全局变量与局部变量撞车我们以往的风格是将树状数组命名为c。而在处理询问时局部变量又定义了int a,b,c,d;。虽然C允许局部变量遮蔽全局变量使得query(c, d)传递的是局部变量但这在工程上是极度危险的做法。强烈建议将全局树状数组命名为cc避免 Bug。数据溢出二维求和极其庞大一定要将ans和cc数组开成long long。七、 题解本题是二维树状数组最纯粹的模板题。通过两层嵌套循环将一维的线段管辖扩展至二维的矩形管辖再辅以二维前缀和的容斥原理用极其轻量级的代码和极小的常数完美解决了二维动态矩阵的维护问题。相比于二维线段树树套树二维树状数组是考场上兼顾速度与代码稳定性的最优解。八、 完整代码#include iostream using namespace std; long long cc[5000][5000];//树状数组 int n,m; //返回x二进制表示下最低位1所代表的整数 int lowbit(int x){ return x(-x); } //树状数组更新操作 void add(int x,int y,int k){ //双层循环x轴和y轴均向上攀升更新所有包含(x,y)的大管辖矩阵 for(int ix;in;ilowbit(i)){ for(int jy;jm;jlowbit(j)){ cc[i][j]k; } } } //树状数组查询操作 //查询左上角为(1,1)右下角为(x,y)的前缀矩阵和 long long query(int x,int y){ long long ret0ll;//记录前缀和 //双层循环x轴和y轴均向下聚拢无缝拼凑出前缀面积 for(int ix;i0;i-lowbit(i)){ for(int jy;j0;j-lowbit(j)){ retcc[i][j]; } } return ret; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; int t; while(cint){ if(t1){//自增操作 int x,y,k; cinxyk; add(x,y,k); } else{//查询操作 int a,b,c,d; cinabcd; //套用二维前缀和容斥原理公式 //务必注意是a-1和b-1否则会多挖掉一行一列 coutquery(c,d)-query(c,b-1)-query(a-1,d)query(a-1,b-1)\n; } } }
