_FastFT2013 @ 2024-01-27 15:06:43
#include<iostream>
#define lowbit(x) (x&(-x))
using namespace std;
const int N=1e5+5;//原数组/树状数组最大长度
template<typename T>
struct Tree_array{
int s=0;
T c[N]={0},ci[N]={0};
void build(T a[],int n){//树状数组预处理(构造) O(n)
s=n;
T fa[n+5],qfa[n+5];
for(int i=1;i<=n;i++){
fa[i]=a[i]-a[i-1];
fa[i]*=i;
qfa[i]=qfa[i-1]+fa[i];
}
for(int i=1;i<=n;i++){
ci[i]=qfa[i]-qfa[i-lowbit(i)];
c[i]=a[i]-a[i-lowbit(i)];
}
}
T find(int x){//单点查询(查询x节点的值) O(log n)
T sum=0;
for(int i=x;i;i-=lowbit(i))sum+=c[i];
return sum;
}
void add_q(int x,int k){//区间修改(将x~n节中点的值加上k) O(log n)
for(int i=x;i<=s;i+=lowbit(i)){
c[i]+=x;
ci[i]+=x*k;
}
}
void add_q(int x,int y,int k){//区间修改(将x~y中节点的值加上k) O(log n)
add_q(x,k),add_q(y+1,-k);
}
void add(int x,int k){//单点修改(将节点x加上k) O(log n)
add_q(x,x,k);
}
T find_q(int x){//区间查询(查询1~x中的和) O(log n)
T sum1=0,sum2=0;
for(int i=x;i;i-=lowbit(i))sum1+=c[i];
sum1*=x+1;
for(int i=x;i;i-=lowbit(i))sum2+=ci[i];
return sum1-sum2;
}
T find_q(int x,int y){//区间查询(查询x~y的和) O(log n)
return find_q(y)-find_q(x-1);
}
};
Tree_array<long long>tree;
long long a[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
tree.build(a,n);
while(m--){
int op;
cin>>op;
if(op==1){
int x,y,k;
cin>>x>>y>>k;
tree.add_q(x,y,k);
}else{
int x,y;
cin>>x>>y;
cout<<tree.find_q(x,y)<<"\n";
}
}
return 0;
}
by Super_Cube @ 2024-01-28 14:47:20
@wuxiuyuan 第 29 行:c[i]+=x
改为 c[i]+=k
。
by _FastFT2013 @ 2024-01-29 08:02:58
谢谢@Super_Cube