线段树模板题总结（1）

本专题总结了线段树的各种应用，参考了胡浩大佬的文章，把代码全部改成了自己的风格。

1. 功能:单点增减，区间求和
   参考例题为HDU1166 敌兵布阵
   https://vjudge.net/problem/HDU-1166

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 54321;
int sum[maxn << 2];

void pushUp(int root) {
    sum[root] = sum[root << 1] + sum[root << 1 | 1];
}

void build(int left, int right, int root) {
    if (left == right) {
        cin >> sum[root];
        return;
    }
    int mid = (left + right) >> 1;
    build(left, mid, root << 1);
    build(mid + 1, right, root << 1 | 1);
    pushUp(root);
}

void update(int pos, int add, int left, int right, int root) {
    if (left == right) {
        sum[root] += add;
        return;
    }
    int mid = (left + right) >> 1;
    if (pos <= mid) update(pos, add, left, mid, root << 1);
    else  update(pos, add, mid+1, right, root << 1 | 1);
    pushUp(root);
}

int query(int L, int R, int left, int right, int root) {
    if (L <= left && right <= R) {
        return sum[root];
    }
    int mid = (left + right) >> 1;
    int res = 0;
    if(L<=mid) res += query(L, R, left, mid, root << 1);
    if(R > mid) res += query(L, R, mid + 1, right, root << 1 | 1);
    return res;
}

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;
}

2. 功能：单点替换，求区间最值
   题目为HDU1754
   https://vjudge.net/problem/HDU-1754

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn = 224321;
int Max[maxn << 2];

void pushUp(int root) {
    Max[root] = max(Max[root << 1] , Max[root << 1 | 1]);
}

void build(int left, int right, int root) {
    if (left == right) {
        cin >> Max[root];
        return;
    }
    int mid = (left + right) >> 1;
    build(left, mid, root << 1);
    build(mid + 1, right, root << 1 | 1);
    pushUp(root);
}

void update(int pos, int change, int left, int right, int root) {
    if (left == right) {
        Max[root] = change;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) update(pos, change, left, mid, root << 1);
    else update(pos, change, mid + 1, right, root << 1 | 1);
    pushUp(root);
}

int query(int L,int R,int left,int right,int root) {
    if (L <= left && right <= R) {
        return Max[root];
    }
    int mid = (left + right) / 2;
    int res = 0;
    if (L <= mid) res = max(res, query(L, R, left, mid, root << 1));
    if (R > mid) res = max(res, query(L, R, mid + 1, right, root << 1 | 1));
    return res;
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        build(1, n, 1);
        while (m--) {
            char op[2];
            int a, b;
            scanf("%s%d%d", op, &a, &b);
            if (op[0] == 'Q') printf("%d\n", query(a, b, 1, n, 1));
            else update(a, b, 1, n, 1);
        }
    }
    return 0;
}

3. 例题HDU2795(注意输入要用c语言才不会超时）
   https://vjudge.net/problem/HDU-2795

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn = 224321;
int Max[maxn << 2];
int h, w, n;

void pushUp(int root) {
    Max[root] = max(Max[root << 1] , Max[root << 1 | 1]);
}

void build(int left, int right, int root) {
    Max[root] = w;
    if (left == right) return;
    int mid = (left + right) >> 1;
    build(left, mid, root << 1);
    build(mid + 1, right, root << 1 | 1);
}

int query(int x, int l, int r, int root) {
    if (l == r) {
        Max[root] -= x;
        return l;
    }
    int mid = (l + r) >> 1;
    int ret = (Max[root << 1] >= x) ? query(x, l,mid,root<<1) : query(x, mid+1, r, root<<1|1);
    pushUp(root);
    return ret;
}


int main() {
    while (~scanf("%d%d%d", &h, &w, &n)) {
        if (h > n) h = n;
        build(1, h, 1);
        while (n--) {
            int x;
            scanf("%d", &x);
            if (Max[1] < x) puts("-1");
            else printf("%d\n", query(x, 1, h, 1));
        }
    }
    return 0;
}