线段树
const int _mxn=1e5+5;
int n;
ll a[_mxn];
struct segtree
{typedef ll dat_type;struct node{int l,r;dat_type dat;dat_type add;int len(){return r-l+1;}}tr[_mxn<<2];inline int ls(int p){return p<<1;}inline int rs(int p){return p<<1|1;}void _pushup(dat_type &pdat,dat_type ldat,dat_type rdat)//{pdat=ldat+rdat;}void _upd(int p,dat_type add)//{tr[p].dat+=add*tr[p].len();tr[p].add+=add;}void pushup(int p){_pushup(tr[p].dat,tr[ls(p)].dat,tr[rs(p)].dat);}void build(int p,int l,int r){tr[p].l=l,tr[p].r=r;tr[p].add=0;if(l==r){tr[p].dat=a[l];return;}int mid=(l+r)>>1;build(ls(p),l,mid);build(rs(p),mid+1,r);pushup(p);}void pushdown(int p){_upd(ls(p),tr[p].add);_upd(rs(p),tr[p].add);tr[p].add=0;//记得清零 tag}void update(int p,int l,int r,dat_type k){if(l<=tr[p].l&&tr[p].r<=r){_upd(p,k);return;}if(r<tr[p].l||tr[p].r<l)return;pushdown(p);update(ls(p),l,r,k);update(rs(p),l,r,k);pushup(p);}dat_type query(int p,int l,int r){if(l<=tr[p].l&&tr[p].r<=r)return tr[p].dat;if(r<tr[p].l||tr[p].r<l)return 0;//pushdown(p);dat_type res;_pushup(res,query(ls(p),l,r),query(rs(p),l,r));return res;}
};
咕咕咕。。。