首页 > 代码库 > 【树状数组区间加+区间查询模板】洛谷P3372
【树状数组区间加+区间查询模板】洛谷P3372
虽然说这道题线段树很好做，但毕竟树状数组常数小又好写，所以还是写个模板吧。
区间加转为前缀加
区间和转为前缀和
我们讨论一个1~k的区间加x对于一个前缀和val【i】的影响
对于所有k<i的更新，对val[i]的贡献为val[i]+=k*x
对于所有k>=i的更新,对val[i]的贡献为val[i]+=i*x
所以我们维护记录两个数组，对于每次更新
a[k]+=x;b[k]+=k*x;
所以对于一个值的前缀和val[i]=b[1~i]+(a[i+1]~a[now])*i;
然后询问的时候前缀减一减就行了
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m;
ll val,f[200000],g[200000],s[200000];
int lowbit(int x){return (x&-x);}
void update1(int x,int v)
{
while (x<=n)
{
f[x]+=v;
x+=lowbit(x);
}
return;
}
void update2(int x,int v)
{
while (x<=n)
{
g[x]+=v;
x+=lowbit(x);
}
return;
}
ll query(int x)
{
ll sum=0;
while (x>0)
{
sum+=f[x];
x-=lowbit(x);
}
return sum;
}
ll query2(int x)
{
ll sum=0;
while (x>0)
{
sum+=g[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
int x;
for (int i=1;i<=n;i++) scanf("%d",&s[i]),s[i]+=s[i-1];
for (int i=1;i<=m;i++)
{
int ch,x,y;
scanf("%d%d%d",&ch,&x,&y);
if (ch==1)
{scanf("%lld",&val);update1(x,val); update1(y+1,-val);
update2(x,x*val);update2(y+1,-(y+1)*val);}
else
{
ll ans1=s[y]+query(y)*(y+1)-query2(y);
ll ans2=s[x-1]+query(x-1)*x-query2(x-1);
printf("%lld\n",ans1-ans2);
}
}
return 0;
}
【树状数组区间加+区间查询模板】洛谷P3372
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。