android软件开发用什么工具_手机网页无法打开是什么原因_百度推广开户联系方式_做百度推广一个月多少钱

#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int n,m,a[N];
struct node{int l,r;ll sum,tag;
}tr[N*4];void pu(int pos){ // push_uptr[pos].sum=tr[pos<<1].sum+tr[pos<<1|1].sum;
}void pd(int pos){ // push_downtr[pos<<1].tag+=tr[pos].tag;tr[pos<<1|1].tag+=tr[pos].tag;tr[pos<<1].sum+=tr[pos].tag*(tr[pos<<1].r-tr[pos<<1].l+1);tr[pos<<1|1].sum+=tr[pos].tag*(tr[pos<<1|1].r-tr[pos<<1|1].l+1);tr[pos].tag=0;
}void build(int pos,int l,int r){tr[pos].l=l;tr[pos].r=r;if(l==r){tr[pos].sum=a[l];return ;}int mid=(l+r)/2;build(pos*2,l,mid);build(pos*2+1,mid+1,r);pu(pos);
}ll ask(int pos,int l,int r){ // [l,r] in [ tr[pos].l , tr[pos].r ]if(tr[pos].l==l&&tr[pos].r==r) return tr[pos].sum;int mid=tr[pos<<1].r;pd(pos);if(l<=mid){if(r>mid) return ask(pos<<1,l,mid)+ask(pos<<1|1,mid+1,r);else return ask(pos<<1,l,r);}else return ask(pos<<1|1,l,r);
}void add(int pos,int l,int r,ll k){ // [l,r] in [ tr[pos].l , tr[pos].r ]if(tr[pos].l==l&&tr[pos].r==r){tr[pos].tag+=k;tr[pos].sum+=k*(r-l+1);return ;}pd(pos);int mid=tr[pos<<1].r;if(l<=mid){if(r>mid) add(pos<<1,l,mid,k),add(pos<<1|1,mid+1,r,k);else add(pos<<1,l,r,k);}else add(pos<<1|1,l,r,k);pu(pos);
}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1;i<=n*4;i++) if(tr[i].l!=0){printf("%d %d %d %lld\n",i,tr[i].l,tr[i].r,tr[i].sum);}// cout<<ask(1,x,y)<<endl;// add(1,x,y,k);return 0;
}

经作者理解注释后

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5; 
struct node
{int l,r;ll sum,tag;
}tr[4*N];
int a[N],n,m;
void pu(int pos)//2.把子节点的sum整合给父节点 
{tr[pos].sum = tr[pos<<1].sum+tr[pos<<1|1].sum;
}
void pd(int pos)
{tr[pos<<1].tag+=tr[pos].tag;tr[pos<<1|1].tag+=tr[pos].tag;tr[pos<<1].sum+=tr[pos].tag*(tr[pos<<1].r-tr[pos<<1].l+1);tr[pos<<1|1].sum+=tr[pos].tag*(tr[pos<<1|1].r-tr[pos<<1|1].l+1);tr[pos].tag=0;//tag已经在pos被用过，其节点已经加过了//下次pos再加给字节tag不能重复加上次的 
}void build(int pos,int l,int r)//1.建树 O(n)
{tr[pos].l=l;tr[pos].r=r;if(l==r)//到树底了 {tr[pos].sum=a[l];return;}int mid=(l+r)/2;build(pos<<1,l,mid);build(pos<<1|1,mid+1,r);pu(pos);
}
ll ask(int pos,int l,int r)
{if(tr[pos].l==l&&tr[pos].r==r){return tr[pos].sum;}int mid = tr[pos<<1].r;pd(pos);//别忘写了 if(l<=mid){if(r>mid) return ask(pos<<1,l,mid)+ask(pos<<1|1,mid+1,r);else return ask(pos<<1,l,r); } else return ask(pos<<1|1,l,r); 
}
void add(int pos,int l,int r,ll k)// 需要加k的区间[l,r] //为了[l,r] in [ tr[pos].l , tr[pos].r ]
{if(tr[pos].l==l&&tr[pos].r==r){tr[pos].tag+=k;tr[pos].sum+=k*(r-l+1);return;}pd(pos);int mid=tr[pos<<1].r;if(l<=mid) //若交叉区间[l,r]左区间 {//同时与右区间有交叉if(r>mid) add(pos<<1,l,mid,k),add(pos<<1|1,mid+1,r,k);else add(pos<<1,l,r,k);//全在左区间 }else add(pos<<1|1,l,r,k);//全在右区间pu(pos); 
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(m--){ll q;cin>>q;if(q==1){int x,y,k;cin>>x>>y>>k;add(1,x,y,k);}if(q==2){int x,y;cin>>x>>y;cout<<ask(1,x,y)<<"\n";}}
}