kuangbin专题线段树

线段树单点修改模板

#include
#include
#include
#include

using namespace std;

const int N = 50010;

struct Node {
    int l, r;
    int sum;
} tr[N * 4];

int w[N];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
    if(l == r) {
        tr[u] = {l, l, w[l]};
    }    
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].sum += v;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid)
            modify(u << 1, x, v);
        else
            modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;
    else {
        int sum = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)
            sum += query(u << 1, l, r);
        if(r > mid)
            sum += query(u << 1 | 1, l, r);
        return sum;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    int id = 0;
    while(T --) {
        printf("Case %d:n", ++id);
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
            scanf("%d", &w[i]);
        build(1, 1, n);
        string op;
        int l, r;
        while(cin >> op , op != "End") {
            scanf("%d%d", &l, &r);
            if(op[0] == 'A')
                modify(1, l, r);
            else if(op[0] == 'S')
                modify(1, l, -r);
            else
                printf("%dn", query(1, l, r));
        }
    }

    return 0;
}

线段树单点修改模板

#include
#include
#include

using namespace std;

const int N = 200010;

struct Node {
    int l, r;
    int v;
} tr[N * 4];

int w[N];

void pushup(int u) {
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r) {
    if(l == r) {
        tr[u] = {l, r, w[l]};
    }
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int val) {
    if(tr[u].l == x && tr[u].r == x) {
        tr[u].v = val;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid)
            modify(u << 1, x, val);
        else
            modify(u << 1 | 1, x, val);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r)
        return tr[u].v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        int maxx = 0;
        if(l <= mid)
            maxx = query(u << 1, l, r);
        if(r > mid)
            maxx = max(maxx, query(u << 1 | 1, l, r));
        return maxx;
    }

} 

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i ++)
            scanf("%d", &w[i]);
        build(1, 1, n);

        while(m --) {
            char op[2];
            int l, r;
            scanf("%s%d%d", op, &l, &r);
            if(op[0] == 'U') {
                modify(1, l, r);
            }
            else {
                printf("%dn", query(1, l, r));
            }
        }
    }

    return 0;
}

线段树区间修改区间查询模板

#include
#include
#include
#include

using namespace std;

const int N = 100010;

typedef long long LL;

struct Node {
    int l, r;
    LL sum, add;
} tr[N * 4];

int w[N];


void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u){
    if(tr[u].add) {
        tr[u << 1].add += tr[u].add, tr[u << 1].sum += (LL)(tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;
        tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].sum += (LL)(tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
        tr[u].add = 0;
        }
}

void build(int u, int l, int r) {
    if(l == r)
        tr[u] = {l, l, w[l], 0};
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d) {
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)
            modify(u << 1, l, r, d);
        if(r > mid)
            modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r){
        return tr[u].sum;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if(l <= mid)
        sum += query(u << 1, l, r);
    if(r > mid)
        sum += query(u << 1 | 1, l, r);
    return sum;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &w[i]);
    }

    build(1, 1, n);

    while(m --) {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if(op[0] == 'Q') {
            printf("%lldn", query(1, l, r));
        }
        else {
            int c;
            scanf("%d", &c);
            modify(1, l, r, c);
        }
    }

    return 0;
}