区间更新

总览

1
2
3
4
5
6
7
8
9
10
11
12
13
#define ls (pos << 1)
#define rs (pos << 1 | 1)
#define mid ((s + t) >> 1)

int n, a[N]; // 区间长度、初值
int tree[N << 2]; // 线段树
int lazy[N << 2]; // lazy数组

inline void push_up(int pos); // 向上更新
inline void push_down(int pos, int s, int t); // 向下更新
void build(int pos, int s, int t); // 建树
void update(int l, int r, int val, int pos, int s, int t); // 区间更新-区间加上val
int query(int l, int r, int pos, int s, int t); // 区间查询-区间和

建树

1
2
3
4
5
6
7
8
9
void build(int pos, int s, int t) {
    if (s == t) {
        tree[pos] = a[s];
        return;
    }
    build(ls, s, mid);
    build(rs, mid + 1, t);
    push_up(pos);
}

push

push_up

1
2
3
inline void push_up(int pos) {
    tree[pos] = tree[ls] + tree[rs];
}

push_down

1
2
3
4
5
6
7
8
9
inline void push_down(int pos, int s, int t) {
    if (lazy[pos]) {
        tree[ls] += lazy[pos] * (mid - s + 1);
        tree[rs] += lazy[pos] * (t - mid);
        lazy[ls] += lazy[pos];
        lazy[rs] += lazy[pos];
        lazy[pos] = 0;
    }
}

修改

[l, r]为更改区间，[s, t]为当前pos点所对应的起始点

区间加上val

1
2
3
4
5
6
7
8
9
10
11
12
13
void update(int l, int r, int val, int pos, int s, int t) {
    if (l <= s && t <= r) {
        tree[pos] += (t - s + 1) * val;
        lazy[pos] += val;
        return;
    }
    push_down(pos, s, t);
    if (l <= mid)
        update(l, r, val, ls, s, mid);
    if (r > mid)
        update(l, r, val, rs, mid + 1, t);
    push_up(pos);
}

查询

1
2
3
4
5
6
7
8
9
10
11
int query(int l, int r, int pos, int s, int t) {
    if (l <= s && t <= r)
        return tree[pos];
    push_down(pos, s, t);
    int sum = 0;
    if (l <= mid)
        sum += query(l, r, ls, s, mid);
    if (r > mid)
        sum += query(l, r, rs, mid + 1, t);
    return sum;
}