线段树

#include <iostream>
using namespace std;

struct node {
    int l, r;
    int max, sum;
    node *lchild, *rchild;
};

int s, t, num;

node * BuildTree(int l, int r, node *now) {
    if (l >= r)return nullptr;
    now->lchild = new node;
    now->rchild = new node;
    if (l == r - 1)return nullptr;
    now->lchild = BuildTree(l, (l + r) / 2, now->lchild);
    now->rchild = BuildTree((l + r) / 2, r, now->rchild);
    now->l = l;
    now->r = r;
    now->max = now->sum = 0;
    return now;
}

int change(int l, int r, node *now) {
    if (now == nullptr)
        return 0;
    if (l >= t || r <= s)return now->max;
    int l_max, r_max;
    if (l >= s&&r <= t) {
        now->sum += num*(r - l);
        now->max += num;
        if (l == r - 1)
            return now->max;
        change(l, (l + r) / 2, now->lchild);
        change((l + r) / 2, r, now->rchild);
        return now->max;
    }
    if (l == r - 1)
        return now->max;
    if (l <= s&&r <= t) 
        now->sum += (r - s)*num;
    if (l >= s&&r >= t) 
        now->sum += (t - l)*num;
    if (l >= s&&r <= t) 
        now->sum += (r - l)*num;
    l_max = change(l, (l + r) / 2, now->lchild);
    r_max = change((l + r) / 2, r, now->rchild);
    now->max = l_max > r_max ? l_max : r_max;
    return now->max;
}

int get_sum(int l, int r, node *now) {
    if (now == nullptr)
        return 0;
    if (l >= t || r <= s)return now->sum;
    if (l >= s&&r <= t)
        return now->sum;
    if (l == r - 1)
        return now->sum;
    return get_sum(l, (l + r) / 2, now->lchild) + get_sum((l + r) / 2, r, now->rchild);
}

int get_max(int l, int r, node *now) {
    if (now == nullptr)
        return 0;
    if (l >= t || r <= s)return -10000000;
    int l_max, r_max;
    if (l >= s&&r <= t)
        return now->max;
    if (l == r - 1)
        return now->max;
    l_max = get_max(l, (l + r) / 2, now->lchild);
    r_max = get_max((l + r) / 2, r, now->rchild);
    int max_num = l_max > r_max ? l_max : r_max;
    return max_num;
}

int main() {
    node *head = new node;
    int n;
    int left, right;
    cin >> left >> right;
    char a;
    BuildTree(left, right, head);
    cin >> n;
    while (n--) {
        cin >> a;
        if (a == 'c') {
            cin >> s >> t >> num;
            change(left, right, head);
        }
        if (a == 'm') {
            cin >> s >> t;
            cout<<get_max(left, right, head)<<endl;
        }
        if (a == 's') {
            cin >> s >> t;
            cout<<get_sum(left, right, head)<<endl;
        }
    }
    system("pause");
    return 0;
}

哪天找道题目测一下，这里涉及到建树、修改、删除、查找四种操作。