注册登录

线段树

建树

struct node {
    int L,R;
    int w;///区间和
    int f;
}t[4*n+1];
void build(int k,int L,int R) {
    t[k].L=L;
    t[k].R=R;
    if(L==R) {
        t[k].w=a[i]; ///叶节点
        return ;
    }
    int m=(L+R)/2;
    build(k*2,L,m);
    build(k*2+1,m+1,R);
    t[k].w=t[k*2].w+t[k*2+1].w;
}
知识兔

懒标记

void down(int k) {
    t[k*2].f+=t[k].f;
    t[k*2+1].f+=t[k].f;
    t[k*2].w+=t[k].f*(t[k*2],R-t[k*2].L+1);
    t[k*2+1].w+=t[k].f*(t[k*2+1].R-t[k*2+1].L+1);
    t[k].f=0;
}
知识兔

单点查询

void ask(int k) {
    if(t[k].L==t[k].R) {
        ans=t[k].w;
        return ;
    }
    if(t[k].f) down(k);
    int m=(t[k].L+t[k].R)/2;
    if(x<=m) ask(k*2);
    else ask(k*2+1);
}
知识兔

单点修改，对第k个数加上y

void add(int k) {
    if(t[k].L==t[k].R) {
        t[k].w+=y;
        return ;
    }
    if(t[k].f) down(k);
    int m=(t[k].L+t[k].R)/2;
    if(x<=m) add(k*2);
    else add(k*2+1);
    t[k].w=t[k*2].w+t[k*2+1].w;
}
知识兔View Code

区间查询 求x到y区间内的和

void getsum(int k) {
    if(t[k].L>=x&&t[k].R<=y) {
        ans+=t[k].w;
        return ;
    }
    if(t[k].f) down(k);
    int m=(t[k].L+t[k].R)/2;
    if(a<=m) getsum(k*2);
    if(b<m) getsum(k*2+1);
}
知识兔View Code

区间修改 给区间a到b的每个数都加上x，修改的时候只修改对查询有用的点

void changesum(int k) {
    if(t[k].L>=a&&t[k].R<=b) {
        t[k].w+=(t[k].R-t[k].L+1)*y;
        t[k].f+=y;
        return ;
    }
    if(t[k].f) down(k);
    int m=(t[k].L+t[k].R)/2;
    if(a<=m) changesum(k*2);
    if(b>m) changesum(k*2+1);
    t[k].w=t[k*2].w+t[k*2+1].w;
}
知识兔View Code
计算机