核心内容摘要
粉色晶体，点亮未来：苏州晶体公司的创新之路
题目描述解决了助教给出的第一个问题后小陶对数据结构的兴趣被点燃了他央求助教给他出了第二个问题给出一个有n个元素的序列n200000进行m次操作操作有两种类型1 x y c 给都加上c2 x输出的值输入格式第一行两个整数n,m接下来m行每行2个或4个整数表示一个操作格式见题面输出格式对于每个操作2输出对应的结果样例【样例僌】5 5 1 5 4 2 3 1 2 4 2 2 3 1 1 5 -1 1 3 5 7 2 4【样例输出】6 10数据范围与提示对于30%的数据 n5000对于60%的数据 n30000对于100%的数据 n200000一些想法这道题依旧用树状数组做。
但是他用到了区间修改和的思想具体看上一篇。
这次的树状数组是差分数组差分数组是用当前数减上一个数得来的。
代码解析输入序列的每一个数在第 i 个位置增加当前数减上一个数的值也就是将当前数减上一个数的值放进树状数组然后上一个数更新为当前数为下次相减提供数据。
然后循环输入操作如果操作类型是 1输入左边界、右边界和增加的值然后左边界到 n 增加右边界加一到 n 减因为要求的是左边界到右边界但是修改函数是某个数到最后一个值都增加这就不符合题目要求所以我们先将左边界到 n 照常增加然后将右边界后一个值负增加这样就只会增加左边界到右边界的数右边界后面的数会被抵消这样就能达到目的了。
如果是查询操作这个直接查询第 x 个数就行了直接调用函数输出就行了。
自定义函数部分lowbit 函数用位运算找 x 二进制的最后一个 1 。
树状数组的所有操作都基于 lowbit 实现区间划分。
查询函数查询 x然后只要 x 大于 0没有超出范围然后将 x 不断减小减自己的lowbit跳转到前一个区间将数增加。
简单来说就是分解将当前区间不断分解成多个小区间查询 a[x] 也就是 x 在树状数组中的表示的数直接调用就行了。
修改函数将第 x 个数增加 y 因为前面的点有变化所以包含这个点的在范围内的所有数都要跟着变化因为父节点要随着子节点的变化而变化所以每次增加自己的 lowbit 也就是不断往后一个区间直到达到边界然后每一个区间都增加指定值。
AC代码#includebits/stdc.h using namespace std; long long n,m,c[200005]; int lowbit(int x){ return x-x; } void zs(int x,int y){ for(;xn;xlowbit(x)) c[x]y; } int sm(int x){ int sum0; for(;x0;x-lowbit(x)) sumc[x]; return sum; } int main(){ cinnm; int r,l,x,op,last,now; for(int i1;in;i){ cinnow; zs(i,now-last); lastnow; } for(int i1;im;i){ cinop; if(op