DDOSvoid's Blog

标记永久化

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

简介

标记永久化一般多用于线段树

大概的思想就是不进行 $pushdown$ 操作，将标记永久的挂在节点上

在使用标记永久化时大部分情况不进行 $maintain$ 操作

如果一定要进行 $maintain$ 的话，注意到一定要在 $maintain$ 的时候把当前点的标记算上

优势

  1. 不需要 $pushdown$，常数略小
  2. 在可持久化或者树套树时不需要新建节点

劣势

  1. 标记有优先级的情况下，不能使用标记永久化（待确定

    我理解的原因是标记总是挂在被包含的区间中，不能保证顺序

例题

区间加 区间求和

Luogu P3372 【模板】线段树 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    T[i].v += (ll) (min(r, R) - max(L, l) + 1) * v;
    if (L <= l && r <= R) return (void) (T[i].add += v);
    int m = l + r >> 1;
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}

ll query(int i, int l, int r, int L, int R, ll add) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v + (r - l + 1) * add;
    int m = l + r >> 1;
    return query(lc, l, m, L, R, add + T[i].add) + query(rc, m + 1, r, L, R, add + T[i].add);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void maintain(int i, int l, int r) { T[i].v = T[lc].v + T[rc].v + T[i].add * (r - l + 1); }

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return (void) (T[i].v += v * (r - l + 1), T[i].add += v);
    int m = l + r >> 1;
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i, l, r);
}

int query(int i, int l, int r, int L, int R, int add) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v + add * (r - l + 1);
    int m = l + r >> 1;
    return query(lc, l, m, L, R, add + T[i].add) + query(rc, m + 1, r, L, R, add + T[i].add);
}

区间加等差数列 区间求和

Luogu P1438 无聊的数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void update(int i, int l, int r, int L, int R, ll k, ll d) {
    int m = l + r >> 1, Len = R - L + 1;
    T[i].v += (2 * k + (Len - 1) * d) * Len / 2;
    if (l == L && r == R) return (void) (T[i].k += k, T[i].d += d); 
    if (R <= m) update(lc, l, m, L, R, k, d);
    else if (L > m) update(rc, m + 1, r, L, R, k, d);
    else {
        update(lc, l, m, L, m, k, d);
        update(rc, m + 1, r, m + 1, R, k + (m + 1 - L) * d, d);
    }
}

ll query(int i, int l, int r, int L, int R) {
    int m = l + r >> 1; ll s = (2 * T[i].k + (R + L - 2 * l) * T[i].d) * (R - L + 1) / 2;
    if (l == L && r == R) return T[i].v;
    if (R <= m) return s + query(lc, l, m, L, R);
    else if (L > m) return s + query(rc, m + 1, r, L, R);
    else return s + query(lc, l, m, L, m) + query(rc, m + 1, r, m + 1, R);
}

区间加 区间求max

由此题不难看出在什么时候标记永久化需要maintain

如果对于指定区间的修改可以在与当前区间仅仅是相交而不是包含的情况下可以直接完成，就不需要maintain

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void maintain(int i) { T[i].v = max(T[lc].v, T[rc].v) + T[i].add; }

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return (void) (T[i].v += v, T[i].add += v);
    int m = l + r >> 1;
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i);
}

int query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1;
    return T[i].add + max(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));
}