难道这不是线段树吗?
其实就是。
给定一个长度为 的数组,让你求出它的和。
我们知道,区间修改,区间查询,线段树的 是最快的。
所以我们选择线段树。
时间复杂度 ,一点不比直接算慢。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
struct tree{
int tag=0,sum=0;
}tr[N*4];
int a[N],n,m;
void push(int l,int r,int id){
int mid=(l+r)>>1,tg=tr[id].tag;
tr[id<<1].sum+=(mid-l+1)*tg;
tr[id<<1|1].sum+=(r-mid)*tg;
tr[id<<1].tag+=tg;
tr[id<<1|1].tag+=tg;
tr[id].tag=0;
}
void add(int l,int r,int s,int t,int k,int id){
if(l<=s&&t<=r){
tr[id].tag+=k;
tr[id].sum+=(t-s+1)*k;
return;
}
push(s,t,id);
int mid=(s+t)>>1;
if(l<=mid)add(l,r,s,mid,k,id<<1);
if(r>mid)add(l,r,mid+1,t,k,id<<1|1);
tr[id].sum=tr[id<<1].sum+tr[id<<1|1].sum;
}
int query(int l,int r,int s,int t,int id){
if(l<=s&&t<=r)return tr[id].sum;
push(s,t,id);
int ans=0;
int mid=(s+t)>>1;
if(l<=mid)ans+=query(l,r,s,mid,id<<1);
if(r>mid)ans+=query(l,r,mid+1,t,id<<1|1);
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
n=2;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,i,1,n,a[i],1);
}
cout<<query(1,n,1,n,1);
}
暂无评论