线段树模板

#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N = 1e5 + 1;
// const int MAX_N = 1e2 + 1;
typedef long long LL;
LL num[MAX_N], tree[MAX_N << 2], tag[MAX_N << 2];
// 对 [l,r] 区间建立线段树,当前根的编号为 nowIndex
void build(int l, int r, int nowIndex){
    if (l == r){
        tree[nowIndex] = num[l];
        return ;
    }
    int mid = l + r >> 1;
    // 后序遍历的方式进行建树
    build(l, mid, nowIndex << 1), build(mid + 1, r, nowIndex << 1 | 1);
    tree[nowIndex] = tree[nowIndex << 1] + tree[nowIndex << 1 | 1];
}
//更新[l,r]区间（每个元素加上k），编号为 nowIndex 的节点记录[L, R]的区间和
void update(int l, int r, int L, int R, int nowIndex, LL k){
    // 如果当前区间是待修改区间的子集的时候，打上标记、更改节点值后直接返回
    if (l <= L && R <= r){
        tree[nowIndex] += (R - L + 1) * k, tag[nowIndex] += k;
        return;
    }
    int mid = L + R >> 1, leftNode = nowIndex << 1, rightNode = nowIndex << 1 | 1;
    // 当前节点不是叶子结点、标记不为空的时候
    if (tag[nowIndex] && L != R){
        // 将标记下传并且更新左右节点
        tree[leftNode]  += tag[nowIndex] * (mid - L + 1), tree[rightNode] += tag[nowIndex] * (R - mid);
        tag[leftNode] += tag[nowIndex], tag[rightNode] += tag[nowIndex];
        // 清空当前节点的标记
        tag[nowIndex] = 0;
    }
    //如果左儿子代表的区间 [L,mid] 与修改区间有交集,则递归更新左儿子
    if (l <= mid)update(l, r, L, mid, leftNode, k);
    //如果右儿子代表的区间 [mid + 1,R] 与修改区间有交集,则递归更新左儿子
    if (r >= mid + 1)update(l, r, mid + 1, R, rightNode, k);
    tree[nowIndex] = tree[leftNode] + tree[rightNode];
}
//查询[l,r]区间，编号为 nowIndex 的节点记录[L, R]的区间和
LL getSum(int l, int r, int L, int R, int nowIndex){
    // 如果当前区间是待查询区间的子集的时候，直接返回
    if (l <= L && R <= r)return tree[nowIndex];
    int mid = L + R >> 1, leftNode = nowIndex << 1, rightNode = nowIndex << 1 | 1;
    if (tag[nowIndex] && L != R){
        // 将标记下传并且更新左右节点
        tree[leftNode]  += tag[nowIndex] * (mid - L + 1), tree[rightNode] += tag[nowIndex] * (R - mid);
        tag[leftNode] += tag[nowIndex], tag[rightNode] += tag[nowIndex];
        // 清空当前节点的标记
        tag[nowIndex] = 0;
    }
    LL sum = 0;
    //如果左儿子代表的区间 [L,mid] 与查询区间有交集,则递归查询左儿子
    if (l <= mid)sum = getSum(l, r, L, mid, leftNode);
    //如果右儿子代表的区间 [mid + 1,R] 与查询区间有交集,则递归查询左儿子
    if (r >= mid + 1)sum += getSum(l, r, mid + 1, R, rightNode);
    return sum;    
}