zkw 线段树
应急时使用。
单点加、区间和
#define lp p<<1
#define rp p<<1|1
int st[MAXN<<2],N=1;
il void bld(int n){while(N<=n+1) N<<=1;memcpy(st+N+1,a+1,n<<2);for(int p=N-1;p;p--) st[p]=st[lp]+st[rp];
}
il void chg(int x,int k){for(x+=N;x;x>>=1) st[x]+=k;
}
il int sum(int l,int r){int res=0;for(l=N+l-1,r=N+r+1;l^r^1;l>>=1,r>>=1){if(~l&1) res+=st[l^1];if(r&1) res+=st[r^1];}return res;
}
单点修改、区间最值
#define lp p<<1
#define rp p<<1|1
int mx[MAXN<<2],N=1;
il void bld(int n){while(N<=n+1) N<<=1;memcpy(st+N+1,a+1,n<<2);for(int p=N-1;p;p--) st[p]=max(st[lp],st[rp]);
}
il void chg(int p,int k){mx[p+=N]+=k;for(p>>=1;p;p>>=1) mx[p]=max(mx[lp],mx[rp]);
}
il int amx(int l,int r){int res=0;for(l=N+l-1,r=N+r+1;l^r^1;l>>=1,r>>=1){if(~l&1) res=max(res,mx[l^1]);if(r&1) res=max(res,mx[r^1]);}return res;
}