模板#11

www.luogu.com.cn

代码

init

1
2
3
4
5
6
7
8
9
#define lc u << 1
#define rc u << 1 | 1

int a[N]; // 初始数组
struct Tree
{
    int l, r, sum; // 分别表示左儿子，右儿子的节点以及该节点的区间和
    int add;		  // 懒惰标记
} tr[N << 2];      // 切记要开4 * n 的存储空间

pushup

1
2
3
4
inline void pushup(int u)
{
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}

build

1
2
3
4
5
6
7
8
9
10
11
12
13
void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l == r)
    {
        tr[u].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(u);
}

pushdown

1
2
3
4
5
6
7
void pushdown(int u)
{
    tr[lc].tag += tr[u].tag, tr[rc].tag += tr[u].tag;
    tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[u].tag;
    tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[u].tag;
    tr[u].tag = 0;
}

dot_update

1
2
3
4
5
6
7
8
9
10
11
12
void dot_update(int u, int x, int k)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        tr[u].sum += k;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) dot_update(lc, x, k);
    if (x > mid) dot_update(rc, x, k);
    pushup(u);
}

section_update

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void modify(int u, int l, int r, int k)
{    
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        tr[u].tag += k;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(lc, l, r, k);
    if (r > mid)
        modify(rc, l, r, k);
    pushup(u);
}

query

1
2
3
4
5
6
7
8
9
10
11
12
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;
    pushdown(u);
    int res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res += query(lc, l, r);
    if (r > mid) res += query(rc, l, r);
    pushup(u);
    return res;
}