线段树模板

成段更新:

#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 111111;
LL addv[maxn<<2];
LL sumv[maxn<<2];
//int maxv[maxn<<2];
void PushUp(int rt) {
//    maxv[rt] = max(maxv[rt<<1], maxv[rt<<1|1]);
    sumv[rt] = sumv[rt<<1] + sumv[rt<<1|1];
}
void PushDown(int rt,int m) {
    if (addv[rt]) {
        addv[rt<<1] += addv[rt];
        addv[rt<<1|1] += addv[rt];
        sumv[rt<<1] += addv[rt] * (m - (m >> 1));
        sumv[rt<<1|1] += addv[rt] * (m >> 1);
        // maxv[rt<<1] += addv[rt];
        // maxv[rt<<1|1] += addv[rt];
        addv[rt] = 0;
    }
}
void build(int l,int r,int rt) {
    addv[rt] = 0;
    if (l == r) {
        scanf("%I64d",&sumv[rt]);
        //scanf("%d", &maxv[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt) {
    if (L <= l && r <= R) {
        addv[rt] += c;
        sumv[rt] += (LL)c * (r - l + 1);
        //maxv[rt] += c
        return ;
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L , R , c , lson);
    if (m < R) update(L , R , c , rson);
    PushUp(rt);
}
LL query(int L,int R,int l,int r,int rt) {
    if (L <= l && r <= R) {
        //return maxv[rt];
        return sumv[rt];
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    LL ret = 0;
    if (L <= m) ret += query(L, R, lson);
                //ret = max(ret, query(L , R , lson));
                
    if (m < R)  ret += query(L, R, rson);
                //ret = max(ret, query(L , R , rson));
                
    return ret;
}
int main() {
    int N , Q;
    scanf("%d%d",&N,&Q);
    build(1 , N , 1);
    while (Q --) {
        char op[2];
        int a , b , c;
        scanf("%s",op);
        if (op[0] == 'Q') {
            scanf("%d%d",&a,&b);
            printf("%I64d
",query(a , b , 1 , N , 1));
        } else {
            scanf("%d%d%d",&a,&b,&c);
            update(a , b , c , 1 , N , 1);
        }
    }
    return 0;
}
View Code

成段置值:

#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 111111;
int h , w , n;
int col[maxn<<2];
int sum[maxn<<2];
void PushUp(int rt) {
       sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(int rt,int m) {
       if (col[rt]) {
              col[rt<<1] = col[rt<<1|1] = col[rt];
              sum[rt<<1] = (m - (m >> 1)) * col[rt];
              sum[rt<<1|1] = (m >> 1) * col[rt];
              col[rt] = 0;
       }
}
void build(int l,int r,int rt) {
       col[rt] = 0;
       sum[rt] = 1;
       if (l == r) return ;
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
       PushUp(rt);
}
int query(int L,int R,int l,int r,int rt) {//求和写法，参数信息=>(问询区间左端点，问询区间右端点，总区间左端点，总区间右端点，根节点编号)
    if (L <= l && r <= R) {
        return sumv[rt];
    }
    int m = l + ((r - l)>>1);
    int ret = 0;
    if (L <= m) ret += query(L , R , lson);
    if (R > m) ret += query(L , R , rson);
    return ret;
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              col[rt] = c;
              sum[rt] = c * (r - l + 1);
              return ;
       }
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (R > m) update(L , R , c , rson);
       PushUp(rt);
}

int main() {
       int T , n , m;
       scanf("%d",&T);
       for (int cas = 1 ; cas <= T ; cas ++) {
              scanf("%d%d",&n,&m);
              build(1 , n , 1);
              while (m --) {
                     int a , b , c;
                     scanf("%d%d%d",&a,&b,&c);
                     update(a , b , c , 1 , n , 1);
              }
              printf("Case %d: The total value of the hook is %d.
",cas , sum[1]);
       }
       return 0;
}
View Code

单点更新:

/*
说明:
此模板支持对于线段的单点加减操作更新、区间最值or和的查询
下面主要以求和操作为例，注释部分为求最值功能，根据自己的
需求适当修改模板

验证题目:HDU 1166 敌兵布阵 (以下代码也是解决此题的代码)
*/
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 50005;//maxn = 线段的最大长度 则=> maxn<<2 = 线段树可能的最多结点
//int maxv[maxn<<2];//保存最大值
//int minv[maxn<<2];//保存最小值
int sumv[maxn<<2];//保存区间和
void PushUP(int rt) {
    //maxv[rt] = max(maxv[rt<<1] , maxv[rt<<1|1]);
    //minv[rt] = min(minv[rt<<1], minv[rt<<1|1]);
    sumv[rt] = sumv[rt<<1] + sumv[rt<<1|1];
}
void build(int l,int r,int rt) {//设置初始值
    if (l == r) {
        // scanf("%d",&maxv[rt]);
        // scanf("%d", &minv[rt]);
        scanf("%d", &sumv[rt]);
        return ;
    }
    int m = l + ((r - l)>>1);
    build(lson);
    build(rson);
    PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt) {//单点更新，参数(更新点，更新值，总区间左端点，总区间右端点，根节点编号)
    if (l == r) {
        //maxv[rt] = sc;
        //minv[rt] = sc;
        sumv[rt] += sc;
        return ;
    }
    int m = l + ((r - l)>>1);
    if (p <= m) update(p , sc , lson);
    else update(p , sc , rson);
    PushUP(rt);
}
// int query(int L,int R,int l,int r,int rt) {//查询最大值的写法、最小值同理、求和区间写法在下面
//     if (L <= l && r <= R) {
//         return maxv[rt];
//     }
//     int m = (l + r) >> 1;
//     int ret = 0;
//     if (L <= m) ret = max(ret , query(L , R , lson));
//     if (R > m) ret = max(ret , query(L , R , rson));
//     return ret;
// }
int query(int L,int R,int l,int r,int rt) {//求和写法，参数信息=>(问询区间左端点，问询区间右端点，总区间左端点，总区间右端点，根节点编号)
    if (L <= l && r <= R) {
        return sumv[rt];
    }
    int m = l + ((r - l)>>1);
    int ret = 0;
    if (L <= m) ret += query(L , R , lson);
    if (R > m) ret += query(L , R , rson);
    return ret;
}
int main(void)
{
    int nCase;
    scanf("%d", &nCase);
    for(int t = 1; t <= nCase; t++){
        memset(sumv, 0, sizeof(sumv));
        int len;
        scanf("%d", &len);
        build(1, len, 1);
        char s[20];
        printf("Case %d:
", t);
        while(~scanf("%s", s) && s[0] != 'E'){//s != 'End'
            if(s[0] == 'Q'){//s = Query
                int L, R;
                scanf("%d %d", &L, &R);
                printf("%d
", query(L, R, 1, len, 1));
            }
            else if(s[0] == 'S'){//减操作
                int point, val;
                scanf("%d%d", &point, &val);
                update(point, -val, 1, len, 1);
            }
            else if(s[0] == 'A'){//加操作
                int point, val;
                scanf("%d%d", &point, &val);
                update(point, val, 1, len, 1);
            }
        }
    }
    return 0;
}
View Code

融合置值和成段加减 ( 刘汝佳程序 ) :

#include<bits/stdc++.h>
#define LL long long
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;

const int maxn = 1e5 + 10;
const int maxnode = maxn<<2;


struct IntervalTree {
    LL _sum, _min, _max;
    LL sumv[maxnode], minv[maxnode], maxv[maxnode], setv[maxnode], addv[maxnode];
    void maintain(int L, int R, int rt) {
        int lc = rt<<1, rc = rt<<1|1;
        if(R > L) {
            sumv[rt] = sumv[lc] + sumv[rc];
            minv[rt] = min(minv[lc], minv[rc]);
            maxv[rt] = max(maxv[lc], maxv[rc]);
        }
        if(setv[rt] >= 0) { minv[rt] = maxv[rt] = setv[rt]; sumv[rt] = setv[rt] * (R-L+1); }
        if(addv[rt]) { minv[rt] += addv[rt]; maxv[rt] += addv[rt]; sumv[rt] += addv[rt] * (R-L+1); }
    }

    void pushdown(int rt) {
        int lc = rt*2, rc = rt*2+1;
        if(setv[rt] >= 0) {
            setv[lc] = setv[rc] = setv[rt];
            addv[lc] = addv[rc] = 0;
            setv[rt] = -1;
        }
        if(addv[rt]) {
            addv[lc] += addv[rt];
            addv[rc] += addv[rt];
            addv[rt] = 0;
        }
    }

    ///update(更新区间左右端点、更新值、更新选项 op = 1 为加减 op != 1 为置值、当前区间左右端点、根)
    void update(int L, int R, LL v, int op, int l, int r, int rt){
        int lc = rt<<1, rc = rt<<1|1;
        if(L <= l && R >= r) {
            if(op == 1) addv[rt] += v;
            else { setv[rt] = v; addv[rt] = 0; }
        } else {
            pushdown(rt);
            int m = l + (r-l)/2;
            if(L <= m) update(L, R, v, op, lson); else maintain(lson);
            if(R > m) update(L, R, v, op, rson); else maintain(rson);
        }
        maintain(l, r, rt);
    }

    ///query(问询的左右端点、累加lazy_tag的累加量、当前区间左右端点、根)
    void query(int L, int R, LL add, int l, int r, int rt) {
        if(setv[rt] >= 0) {
            LL v = setv[rt] + add + addv[rt];
            _sum += v * (LL)(min(r,R)-max(l,L)+1);
            _min = min(_min, v);
            _max = max(_max, v);
        } else if(L <= l && R >= r) {
            _sum += sumv[rt] + add * (LL)(r-l+1);
            _min = min(_min, minv[rt] + add);
            _max = max(_max, maxv[rt] + add);
        } else {
            int m = l + (r-l)/2;
            if(L <= m) query(L, R, add+addv[rt], lson);
            if(R > m) query(L, R, add+addv[rt], rson);
        }
    }
}T;

int main(void)
{
    int n, q;
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        LL v;
        scanf("%lld", &v);
        T.update(i, i, v, 1, 1, n, 1);
    }

    while(q--){
        int type;
        scanf("%d", &type);
        if(type == 1){
            int pos;
            scanf("%d", &pos);
            LL v;
            scanf("%lld", &v);
            T.update(pos, pos, v, 2, 1, n, 1);
        }else if(type == 2){
            LL v;
            scanf("%lld", &v);
            T.update(1, n, v, 1, 1, n, 1);
        }else{
            int pos;
            scanf("%d", &pos);
            T._sum = 0;
            T.query(pos, pos, 0, 1, n, 1);
            printf("%lld
", T._sum);
        }
    }
    return 0;
}
View Code

此程序是这题 ==> 戳这里 的代码、可以验模板正确性

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qwertiLH/p/8097607.html