线段树模板

https://www.cnblogs.com/xenny/p/9801703.html

#include<iostream>
using namespace std;
const int maxn = 1e4 + 10;
int a[maxn], t[maxn << 2], lazy[maxn << 2];
void build(int root, int l, int r)
{
    if (l == r)
    {
        t[root] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(root * 2, l, m);
    build(root * 2 + 1, m + 1, r);
    t[root] = t[root * 2] + t[root * 2 + 1];
}
void update(int p, int val, int l, int r, int root)
{
    if (l == r)
    {
        t[l] += val;
        return;
    }
    int m = (l + r) / 2;
    if (p < m)update(p, val, l, m, root);
    else if (p > m)update(p, val, m + 1, r, root);
    t[root] = t[root * 2] + t[root * 2 + 1];
}
int query(int L, int R, int l, int r, int root)
{
    if (L <= l && r <= R)
    {
        return t[root];
    }
    int res = 0;
    int mid = (l + r) / 2;
    if (L < mid)res += query(L, R, l, mid, root * 2);
    if (R > mid)res += query(L, R, mid + 1, r, root * 2 + 1);
    return res;
}

void pushdown(int root)
{
    if (lazy[root])
    {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
        t[root * 2] += lazy[root * 2];
        t[root * 2 + 1] += lazy[root * 2 + 1];
        lazy[root] = 0;
    }
}
void updatelazy(int L,int R,int val,int l,int r,int root){
    if (L <= l && r <= R) {
        lazy[root] += val;
        return;
    }
    pushdown(root);
    int mid = (l + r) / 2;
    if (L <= mid)update(L, R, val, l, mid, root * 2);
    if (R > mid)update(L, R, val, mid + 1, R, root * 2 + 1);
    t[root] = t[root * 2] + t[root * 2 + 1];
}
int querylazy(int L, int R, int l, int r, int root)
{
    if (L <= l && r <= R)
    {
        return t[root];
    }
    pushdown(root);
    int res = 0;
    int mid = (l + r) / 2;
    if (L <= mid)res += querylazy(L, R, l, mid, root * 2);
    if (R > mid)res += querylazy(L, R, mid + 1, r, root * 2 + 1);
    return res;
}