线段树"捉虫“
当前没有测试数据。
建树代码
void build(int p,int l,int r){
if(l==r){
tree[p].sum=l;
return ;
}
int mid=(l+r)/2;
build(p2,l,mid);
build(p*2+1,mid+1,r);
}
标记传递代码
void spread(int p){
if(!tree[p].add){
tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l);
tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l);
tree[p*2].add=tree[p].add;
tree[p*2+1].add=tree[p].add;
}
}
修改代码
void change(int p,int l,int r,int d){
if(l<=tree[p].l&&r>=tree[p].r){
tree[p].sum+=(long long)d*(tree[p].r-tree[p].l+1);
return;
}
spread(p);
int mid=(l+r)/2;
if(l<=mid) change(p*2,l,r,d);
if(r>mid) change(p*2+1,l,r,d);
}
查询代码
void ask(int p,int l,int r){
if(l<=tree[p].l&&r>=tree[p].r) return tree[p].sum;
spread(p);
int mid=(tree[p].l+tree[p].r)/2;
long long val=0;
if(l<=mid) ask(p*2,l,r);
if(r>mid) ask(p*2+1,l,r);
return val;
}