线段树

· · 算法·理论

建树：

void build(int s,int t,int p){//对[s,t]区间建立线段树,当前根的编号为 p
    if(s==t){//如果查到叶子节点
        d[p]=a[s];//基层初始化
        return;//该路结束
    }
    int m=s+((t-s)>>1);//计算分割点//中点
    // 移位运算符的优先级小于加减法，所以加上括号
    // 如果写成 (s + t) >> 1 可能会超出 int 范围
    build(s,m,p*2),build(m+1,t,p*2+1);
    // 递归对左右区间建树
    d[p]=d[p*2]+d[(p*2)+1];//初始化
}
void build(int s,int t,int p){
    if(s==t){
        d[p]=a[s];
        //懒标记
        return;
    }
    int m=s+((t-s)>>1);
    build(s,m,p*2),build(m+1,t,p*2+1);
    d[p]=d[p*2]+d[(p*2)+1];
}

区间查询：

int getsum(int l, int r, int s, int t, int p) {
    // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if(l<=s && t<=r){
        return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
    }
    int m=s+((t-s)>>1),sum=0;
    ①//下放懒标记
    if(l<=m) sum+=getsum(l,r,s,m,p*2);
    // 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
    if(r>m) sum+=getsum(l,r,m+1,t,p*2+1);
    // 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
    return sum;
}
int getsum(int l, int r, int s, int t, int p) {
    if(l<=s && t<=r){
        return d[p]; 
    }
    int m=s+((t-s)>>1),sum=0;
    ①
    if(l<=m) sum+=getsum(l,r,s,m,p*2);
    if(r>m) sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}

区间修改：

// [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p为当前节点的编号
void update(int l,int r,int c,int s,int t,int p){
    // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
    if(l<=s && t<=r){//当前区间被目标区间覆盖
        d[p]+=(t-s+1)*c,b[p]+=c;//b:懒标记,d:和
        return;//回去
    }
    int m=s+((t-s)>>1);//中点
    if(b[p] && s!=t){
        // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        d[p*2]+=b[p]*(m-s+1),d[p*2+1]+=b[p]*(t-m);
        b[p*2]+=b[p],b[p*2+1]+=b[p];//将标记下传给子节点
        b[p]=0;//清空当前节点的标记
    }
    if(l<=m) update(l,r,c,s,m,p*2);//向左
    if(r>m) update(l,r,c,m+1,t,p*2+1);//向右
    d[p]=d[p*2]+d[p*2+1];//整合值
}
void update(int l,int r,int c,int s,int t,int p){
    if(l<=s && t<=r){
        d[p]+=(t-s+1)*c,b[p]+=c;
        return;
    }
    int m=s+((t-s)>>1);
    if(b[p] && s!=t){
        d[p*2]+=b[p]*(m-s+1),d[p*2+1]+=b[p]*(t-m);
        b[p*2]+=b[p],b[p*2+1]+=b[p];
        b[p]=0;
    }
    if(l<=m) update(l,r,c,s,m,p*2);
    if(r>m) update(l,r,c,m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}

Tips:此为求区间和版本

矩阵修改：

void changey(int kx,int ky,int l,int r){
    if(y1<=l && r<=y2){
        sum[kx][ky]++;
        return;
    }
    int mid=l+r>>1;
    if(y1<=mid) changey(kx,ky<<1,l,mid);
    if(y2>mid) changey(kx,ky<<1|1,mid+1,r);
}
void changex(int kx,int l,int r){
    if(x1<=l && r<=x2){
        changey(kx,1,1,n);
        return;
    }
    int mid=l+r>>1;
    if(x1<=mid) changex(kx<<1,l,mid);
    if(x2>mid) changex(kx<<1|1,mid+1,r);
}

单查（二维）：

void queryy(int kx,int ky,int l,int r){
    ans+=sum[kx][ky];
    if(l==r) return;
    int mid=ly+ry>>1;
    if(y<=mid) queryy(kx,ky<<1,l,mid);
    else queryy(kx,ky<<1|1,mid+1,r);
}
void queryx(int kx,int l,int r){
    queryy(kx,1,1,n);
    if(l==r) return;
    int mid=l+r>>1;
    if(x<=mid) queryx(kx<<1,l,mid);
    else queryx(kx<<1|1,mid+1,r);
}

赋值系题目懒标记初值赋为-1！

①：

if(b[p] && s!=t){
    d[p*2]+=b[p]*(m-s+1),d[p*2+1]+=b[p]*(t-m);
    b[p*2]+=b[p],b[p*2+1]+=b[p];
    b[p]=0;
}