社区讨论
这题用区间查询+区间修改的方法过得了吗?
P3368【模板】树状数组 2参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lode84eq
- 此快照首次捕获于
- 2023/10/31 05:09 2 年前
- 此快照最后确认于
- 2023/11/06 20:30 2 年前
蒟蒻刚学完树状数组,用区间查询+区间修改的方法TIE了后面两个点,想问一下这题是不是只能用区间修改+单点查询的方法。
附上代码
CPP#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long sum1[503030];
long long sum2[504024];
int a[503030];
int N,M;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int k)
{
int xx=x;
while(x<=N)
{
sum1[x]+=k;
sum2[x]+=(xx-1)*k;
x+=lowbit(x);
}
}
long long search(int x)
{
long long s=0;
int i=x;
while(x>0)
{
s+=i*sum1[x]-sum2[x];
x-=lowbit(x);
}
return s;
}
long long ask(int l,int r)
{
return search(r)-search(l-1);
}
int main()
{
cin>>N>>M;
for(int i=1;i<=N;i++)
{
cin>>a[i];
add(i,a[i]-a[i-1]);
}
for(int i=1;i<=M;i++)
{
int z,l,r,k;
int x;
cin>>z;
if(z==1)
{
cin>>l>>r>>k;
add(l,k);
add(r+1,-k);
}
if(z==2)
{
cin>>x;
cout<<ask(x,x)<<endl;
}
}
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...