线段树

建立节点信息

1
2
3
struct book{
	int l, r, sum = 0, lazy = 0;//区间[l, r], 区间和, 懒标记
}tree[M];

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
//递归建树
void build(int k, int l, int r){
    tree[k].l = l;
    tree[k].r = r;
    if(l == r){
        tree[k].sum = Number[i];
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    update(k);
}

更新

1
2
3
void update(int k){
    tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;
}

区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void change(int k, int l, int r, int x){
    if(tree[k].l == l && tree[k].r == r){
        tree[k].sum += (l - r + 1) * x;//更新当前区间和, 但是不下传
        tree[k].lazy += x;//懒标记
    }
    pushdown(k);//下传
    //分治
    int mid = (tree[k].r - tree[k].l) >> 1;
    if(r <= mid){
        change(k << 1, l, r, x);
    }
    else if(r > mid){
        change(k << 1 | 1,l ,r ,x);
    }
    else{
        change(k << 1, l, mid, x);
        change(k << 1 | 1, mid + 1, r, x);
    }
    update(k);
}

下传

1
2
3
4
5
6
7
8
9
void pushdown(int k){
    if(!tree[k].lazy){
        return;
    }
    tree[k << 1].sum += tree[k].lazy * (tree[k << 1].r - tree[k << 1].l + 1);
    tree[k << 1].lazy += tree[k].lazy;
    tree[k << 1 | 1].sum += tree[k].lazy * (tree[k << 1 | 1].r - tree[k << 1 | 1].l + 1);
    tree[k << 1 | 1].lazy += tree[k].lazy;
}

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Find(int k, int l, int r){
    if(tree[k].l == l && tree[k].r == r){
        return tree[k].sum;
    }
    pushdown(k);
    //分治
    int mid = (tree[k].r - tree[k].l) >> 1;
    if(r <= mid){
        return Find(k << 1, l, r);
    }
    else if(r > mid){
        return Find(k << 1 | 1,l ,r ,x);
    }
    else{
        return Find(k << 1, l, mid, x) + Find(k << 1 | 1, mid + 1, r, x);
    }
}