线段树

线段树是一棵二叉树，每个节点记录相应区间的信息

维护最大值

解决的问题

单点更新，求区间最值，区间和
成段更新，区间求和
二维空间覆盖问题（求覆盖面积，周长）

实现参考NOTONLYSUCCESS

单点更新，区间求和

hdu1166 敌兵布阵

#include <stdio.h>

//maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍
const int maxn = 56000 << 2;
int sum[maxn];

//PushUP(int rt)是把当前结点的信息更新到父结点
//rt表示当前子树的根(root),也就是当前所在的结点
void PushUP(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", sum+rt);
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, rt<<1);
    build(m+1, r, rt<<1|1);
    PushUP(rt);
}
//add i,j
//sub i,j
void update(int p, int add, int l, int r, int rt) {
    if (l == r) {
        sum[rt] += add;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, add, l, m, rt<<1);
    else update(p, add, m+1, r, rt<<1|1);
    PushUP(rt);
}
int Query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        return sum[rt];
    }
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret += Query(L, R, l, m , rt<<1);
    if (R > m) ret += Query(L, R, m+1, r, rt<<1|1);
    return ret;
}

void PushDown(int rt) {

}

int main() {
    int T, n;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        printf ("Case %d:\n", cas);
        scanf("%d", &n);
        build(1, n, 1);
        char op[10];
        while(scanf("%s", op)) {
            if (op[0] == 'E') break;
            int a, b;
            scanf("%d%d", &a, &b);
            if (op[0] == 'Q') printf("%d\n", Query(a, b,1,n,1));
            else if (op[0] == 'S') update(a, -b, 1, n, 1);
            else update(a, b, 1, n, 1);
        }
    }
    return 0;
}

单点更新，区间最值

hdu1754 I Hate It

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

//maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍
const int maxn = 222222 << 2;

class SegTree{
private:
    int sum[maxn];
    int n, m;

public:
    //PushUP(int rt)是把当前结点的信息更新到父结点
    //rt表示当前子树的根(root),也就是当前所在的结点
    void input() {
        while (scanf("%d%d", &n, &m)!=EOF){
            //memset(sum, 0 , sizeof(sum));
            int i;
            build(1, n, 1);
            char op[10];
            while(m--) {
                scanf("%s", op);
                int a, b;
                scanf("%d%d", &a, &b);
                if (op[0] == 'Q') printf("%d\n", Query(a, b,1,n,1));
                else update(a, b, 1, n, 1);
            }
        }
    }
    int Max(const int a, const int b) {
        if (a > b) return a;
        return b;
    }
    void PushUP(int rt) {
        sum[rt] = max(sum[rt<<1], sum[rt<<1|1]);
    }
    void build(int l, int r, int rt) {
        if (l == r) {
            scanf("%d", sum+rt);
            return ;
        }
        int m = (l + r) >> 1;
        build(l, m, rt<<1);
        build(m+1, r, rt<<1|1);
        PushUP(rt);
    }
    //add i,j
    //sub i,j
    void update(int p, int add, int l, int r, int rt) {
        if (l == r) {
            sum[rt] = add;
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) update(p, add, l, m, rt<<1);
        else update(p, add, m+1, r, rt<<1|1);
        PushUP(rt);
    }
    int Query(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) {
            return sum[rt];
        }
        int m = (l + r) >> 1;
        int ret = 0;
        if (L <= m) ret = max(ret, Query(L, R, l, m , rt<<1));
        if (R > m) ret = max(ret, Query(L, R, m+1, r, rt<<1|1));
        return ret;
    }

    void PushDown(int rt) {

    }
};
int main() {
    SegTree S;
    S.input();
    return 0;
}

线段树

线段树

相关推荐