线段树的用处
建立线段树的方法
“`cpp
#defind ll long long
ll a[maxn],w[maxn*4]
void pushup(const int u){
w[u]=w[u*2]+w[u*2+1];
}
void build(const int u,int l,int r){
if(l==r){
w[u]=a[l];
return;
}
int mid=(l+r)/2;
build(u*2,l,m);
build(u*2+1,m+1,r);
pushup(u);
}
“`
单点查询
“`cpp
ll query1(int u,int l,int r,int p){
if(l==r){
return w[u];
}
else{
int mid=(l+r)/2;
if(mid>=p){
return query1(u*2,l,mid,p);
}
else{
return query1(u*2+1,mid+1,r,p);
}
}
}
“`
单点修改
“`cpp
void update1(int u,int l,int r,int p,ll x){
id(l==r){
w[u]=x;
}
else{
int mid=(l+r)/2;
if(mid>=p){
update1(u*2,l,mid,p,x);
}
else{
update1(u*2+1,mid+1,r,p,x);
}
pushup(u);
}
}
“`
区间查询
“`cpp
bool InRange(int L,int R,int l,int r){
return (l<=L)&&(R<=r);
}
bool OutofRange(int L,int R,int l,int r){
return (L>r)||(R<l);
}
ll query(int u,int L,int R,int l,int r){
if(InRange(L,R,l,r)){
return w[u];
}
else if(!OutofRange(L,R,l,r)){
int mid=(L+R)/2;
return query(u*2,L,mid,l,r)+query(u*2+1,mid+1,R,l,r);
}
else{
return 0;
}
}
“`
区间修改
“`cpp
ll lzy[maxn*4];
bool InRange(int L,int R,int l,int r){
return (l<=L)&&(R<=r);
}
bool OutofRange(int L,int R,int l,int r){
return (L>r)||(R<l);
}
void maketag(int u,int len,ll x){
lzy[u]+=x;
w[u]+=len*x;
}
void pushdown(int u,int l,int r){
int mid=(l+r)/2;
maketag(u*2,mid-l+1,lzy[u]);
maketag(U*2+1,r-mid,lzy[u);
lzy[u]=0;
}
ll query(int u,int L,int R,int l,int r){
if(InRange(L,R,l,r)){
maketag(u,R-L+1,x);
}
else if(!OutofRange(L,R,l,r)){
int M=(L+R)/2;
pushdown(n,L,R);
return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
}
else{
return 0;
}
}
void update(int L,int R,int l,int r,ll x){
if(InRange){
maketag(u,R-L+1,x);
}
else if(!OutofRange(L,R,l,r)){
int M=(L+Ｒ)/2;
pushdown(u,L,R);
update(u*2,L,M,l,r,x);
update(u*2+1,M+1,R,l,r,x);
pushup(u);
}
}
“`
没有回复内容