草(中日双语)
by xhhkwy @ 2019-02-08 12:36:13
@[xhhkwy](/space/show?uid=96592) 我知道复杂度啊,这个复杂度确实很高,但是我只会这么写啊
by Fractures @ 2019-02-08 12:37:17
艹(日语)
by Fractures @ 2019-02-08 12:37:44
直接差分就好了吧……
by ywr8 @ 2019-02-08 12:39:22
差分后将单点查询变成前缀和就好了
```cpp
#include<cstdio>
int a[500001];
int n,m,flag,x,y,k;
inline void add(int x,int val)
{for(;x<=n;x+=x&-x)a[x]+=val;}
inline int ask(int x)
{
int ans=0;
for(;x;x-=x&-x)ans+=a[x];
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
y=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
add(i,x-y);
y=x;
}
//for(int i=1;i<=n;++i)printf("%d ",dif[i]);
while(m--)
{
scanf("%d",&flag);
if(flag==1)
{
scanf("%d%d%d",&x,&y,&k);
add(x,k);
add(y+1,-k);
}
if(flag==2)scanf("%d",&x),printf("%d\n",ask(x));
}
return 0;
}
```
by ywr8 @ 2019-02-08 12:41:04
这代码一看就是来钓鱼的。
我没见过哪个人蠢到树状数组要这么修改,这么查询的,你要是把add和sum的方向写反我还能理解,你发这个帖子并且写这份代码只是想造个神贴,对吧?
by Sai0511 @ 2019-02-08 12:51:28
抱歉,我以为是树状数组1
by Sai0511 @ 2019-02-08 12:53:10
@[忠诚的程序猿](/space/show?uid=78791) 这题不是这么做的,能拿70说明数据太水了
by 周子衡 @ 2019-02-08 12:59:33
@[忠诚的程序猿](/space/show?uid=78791)
树状数组基础啊
[传送门](https://www.luogu.org/blog/cqj/bi-ji-shu-zhuang-shuo-zu-xian-duan-shu)
by resftlmuttmotw @ 2019-02-08 13:05:40
火钳刘明
by 周子衡 @ 2019-02-08 13:09:31