NOIp 数据结构专题总结 (2)

系列索引：

• NOIp 数据结构专题总结 (1): https://www.cnblogs.com/greyqz/p/9472917.html
• NOIp 数据结构专题总结 (2): https://www.cnblogs.com/greyqz/p/9541371.html

Binary Indexed Tree

a.k.a. Fenwick Tree.

Pure

WARNING: subscripts must begin with \(1, 2, \cdots, n\).

int lowbit(int x) { return x & (-x); }

void update(int x, int y) {
    for (; x <= N; x += lowbit(x)) t[x] += y;
}

int sum(int x) { // prefix
    int ret = 0;
    for (; x; x -= lowbit(x)) ret += t[x];
    return ret;
}

// query sum of [l, r]
int query(int l, int r) {
    return sum(r) - sum(l-1);
}

2 Dimensions

void update(int x, int y, int z) {
    int i = x;
    while (i <= n) {
        int j = y;
        while (j <= m) {
            t[i][j] += z;
            j += lowbit(j);
        }
        i += lowbit(i);
    }
}

int sum(int x, int y) { // prefix
    int ret = 0, i = x;
    while (i > 0) {
        int j = y;
        while (j > 0) {
            ret += t[i][j];
            j -= lowbit[j];
        }
        i -= lowbit[i];
    }
    return ret;
}

Segment Tree

Pure

int t[N << 2];

void change(int k, int l, int r, int x, int v) {
    if (r < x || l > x) return;
    if (l == r && l == x) {
        t[x] = v; // also: t[x] += v;
        return;
    }
    int mid = (l + r) >> 1;
    change(k<<1, l, mid, x, v);
    change((k<<1)+1, mid+1, r, x, v);
    t[k] = t[k<<1] + t[(k<<1)+1]; // update value (*)
}

int query(int k, int l, int r, int x, int y) {
    if (y < l || x > r) return 0;
    if (l >= x && r <= y) return t[k];
    int mid = (l + r) >> 1, ret;
    ret = query(k<<1, l, mid, x, y);
    ret += query((k<<1)+1, mid+1, r, x, y); // (*)
    return ret;
}

change(1, 1, n, x, val);
query(1, 1, n, l, r);

*: changeable. e.g. sum, max, min.

Lazy Tag

void modify(int k, int l, int r, int x, int y, int v) {
    if (r < x || l > y) return;
    if (l >= x && r <= y) {
        lazy[k] += v; // lazy tag
        return;
    }
    int mid = (l + r) >> 1;
    modify(k<<1, l, mid, x, y, v);
    modify((k<<1)+1, mid+1, r, x, y, v);
}

int query(int k, int l, int r, int x) { // query single point x
    if (l == r) return lazy[k];
    int mid = (l + r) >> 1;
    if (x <= mid) return query(k<<1, l, mid, x) + lazy[k];
    else return query((k<<1)+1, mid+1, r, x) + lazy[k];
}

Push down

void add(int k, int l, int r, int v) {
    lazy[k] += v;
    sum[k] += (r-l+1) * v;
}

void pushdown(int k, int l, int r, int mid) {
    if (!lazy[k]) return;
    add(k<<1, l, mid, lazy[k]);
    add((k<<1)+1, mid+1, r, lazy[k]);
    lazy[k] = 0;
}

void modify(int k, int l, int r, int x, int y, int v) {
    if (l >= x && r <= y) {
        add(k, l, r, v);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(k, l, r, mid);
    if (x <= mid) modify(k<<1, l, mid, x, y, v);
    if (mid < y) modify((k<<1)+1, mid+1, r, x, y, v);
    sum[k] = sum[k<<1] + sum[(k<<1)+1];
}

int query(int k, int l, int r, int x, int y) {
    if (l >= x && r <= y) return sum[k];
    int mid = (l + r) >> 1, ret = 0;
    pushdown(k, l, r, mid);
    if (x <= mid) ret += query(k<<1, l, mid, x, y);
    if (mid < y) ret += query((k<<1)+1, mid+1, r, x, y);
    return ret;
}

同时支持区间乘和区间加：将标记设计为先乘 a 再加 b，那么区间加时直接加 b 即可，而区间乘时需要将 a 和 b 都乘上一个数。

/* Segment Tree: 同时支持区间乘和区间加
 * Au: GG (Luogu P3373)
 */
#include <cstdio>
#define ll long long
const int N = 100002;
int n, m, MOD, data[N], lazy[N<<2], sum[N<<2], lazy2[N<<2];

void build(int k, int l, int r) {
    lazy2[k] = 1;
    if (l==r) { sum[k] = data[l]; return; }
    int mid = l+r >> 1;
    build(k<<1, l, mid);
    build((k<<1)+1, mid+1, r);
    sum[k] = ((ll)sum[k<<1] + sum[(k<<1)+1]) % MOD;
}
void add(int k, int l, int r, int v) {
    lazy[k] = ((ll)lazy[k] + v) % MOD;
    sum[k] = (sum[k] + (ll)(r-l+1) * v) % MOD;
}
void mul(int k, int l, int r, int v) {
    lazy[k] = ((ll)lazy[k] * v) % MOD;
    lazy2[k] = ((ll)lazy2[k] * v) % MOD;
    sum[k] = ((ll)sum[k] * v) % MOD;
}
void pushdown(int k, int l, int r, int mid) {
    if (lazy2[k]!=1) {
        mul(k<<1, l, mid, lazy2[k]);
        mul((k<<1)+1, mid+1, r, lazy2[k]);
        lazy2[k] = 1;
    }
    if (lazy[k]) {
        add(k<<1, l, mid, lazy[k]);
        add((k<<1)+1, mid+1, r, lazy[k]);
        lazy[k] = 0;
    }
}
void modify(int k, int l, int r, int x, int y, int v) {
    if (l>=x && r<=y) {add(k, l, r, v); return;}
    int mid = l+r >> 1;
    pushdown(k, l, r, mid);
    if (x<=mid) modify(k<<1, l, mid, x, y, v);
    if (y>mid) modify((k<<1)+1, mid+1, r, x, y, v);
    sum[k] = ((ll)sum[k<<1] + sum[(k<<1)+1]) % MOD;
}
void modify2(int k, int l, int r, int x, int y, int v) {
    if (l>=x && r<=y) {mul(k, l, r, v); return;}
    int mid = l+r >> 1;
    pushdown(k, l, r, mid);
    if (x<=mid) modify2(k<<1, l, mid, x, y, v);
    if (y>mid) modify2((k<<1)+1, mid+1, r, x, y, v);
    sum[k] = ((ll)sum[k<<1] + sum[(k<<1)+1]) % MOD;
}
int query(int k, int l, int r, int x, int y) {
    if (l>=x && r<=y) return sum[k];
    int mid = l+r >> 1, res = 0;
    pushdown(k, l, r, mid);
    if (x<=mid) res = ((ll)res + query(k<<1, l, mid, x, y)) % MOD;
    if (y>mid) res = ((ll)res + query((k<<1)+1, mid+1, r, x, y)) % MOD;
    return res;
}

int main() {
    scanf("%d%d%d", &n, &m, &MOD);
    for (int i=1; i<=n; i++) 
        scanf("%d", &data[i]);
    build(1, 1, n);
    int opt, a, b, c;
    while (m--) {
        scanf("%d%d%d", &opt, &a, &b);
        if (opt>2) printf("%d\n", query(1, 1, n, a, b));
        else {
            scanf("%d", &c);
            if (opt<2) modify2(1, 1, n, a, b, c);
            else modify(1, 1, n, a, b, c);
        }
    }
    return 0;
}

NOIp 数据结构专题总结 (2)

原文：https://www.cnblogs.com/greyqz/p/9541371.html