- 李定航's Note
线段树的查询区间和更新区间
- 2023-11-3 7:25:10 @
查询区间:
long long cxqj(int x,int l,int r,int cl,int cr){
//x表示节点编号,[l,r]是节点x的区间,[cl,cr]是查询的区间
if(bh(l,r,cl,cr)){
//如果查询的区间包含x的区间
return qjh[x];
//直接返回x的区间和
} else if(!qjwj(l,r,cl,cr)){
//两个区间相交了一部分
int mid=(l+r)/2;
//分左、右子树
pushdown(x,l,r);
//下放懒标记
return cxqj(x*2,l,mid,cl,cr)+cxqj(x*2+1,mid+1,r,cl,cr);
//返回左子树的查询和右子树的查询
} else return 0;
//完全无交
}
更新区间:
void gxqj(int x,int l,int r,int gl,int gr,long long num){
//[l,r]表示节点x的区间,[gl,gr]表示要更新的区间,num表示懒标记
if(bh(l,r,gl,gr)) bj(x,r-l+1,num);
//如果更新的区间包含了节点的区间,那么直接下放节点的懒标记
else if(!qjwj(l,r,gl,gr)){
//相交一部分
int mid=(l+r)/2;
pushdown(x,l,r);
//先下放懒标记
gxqj(x*2,l,mid,gl,gr,num);
//更新左子树
gxqj(x*2+1,mid+1,r,gl,gr,num);
//更新右子树
qjh[x]=qjh[x*2]+qjh[x*2+1];
//更新区间和
//区间和=左子树区间和+右子树区间和
}
}