最朴素的线段树 模板

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;
const int N = 2e5 + 10;
using ll = long long;

int n;
struct node 
{
    int l, r;
    ll sum, lz;
}tree[N << 2];
inline int ls(int cur)
{
    //求左子节点
    return cur << 1;
}
inline int rs(int cur)
{
    //求右子节点
    return (cur << 1) | 1;
}
void push_up(int cur)
{
    //左右子树更新当前区间的值
    tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum;
}
void push_down(int cur)
{
    //在查询时，如果子树的值还未进行更新，则对子树进行更新
    if (tree[cur].lz) {
        tree[ls(cur)].sum += (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].lz;
        tree[ls(cur)].sum += (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].lz;
        tree[ls(cur)].lz += tree[cur].lz;
        tree[rs(cur)].lz += tree[cur].lz;
        tree[cur].lz = 0;
    }
}
void build(int cur, int l, int r)
{
    tree[cur].l = l;
    tree[cur].r = r;
    if (l == r) {
        //已经到了叶子节点
        ll a;
        cin >> a;
        tree[cur].sum = a;
        return;
    }
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    build(ls(cur), l, mid);
    build(rs(cur), mid + 1, r);
    push_up(cur);
}

void update(int cur, int l, int r, int v) 
{
    if (tree[cur].l == l and tree[cur].r == r) {
        //当前节点正好是要修改的区间
        tree[cur].sum += (r - l + 1) * v;
        tree[cur].lz += v;
        return;
    }
    //遍历到当前节点时，顺便将子节点的值给更新
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        //要更新的区间都在当前节点区间的左边
        update(ls(cur), l, r, v);
    }
    else if (l > mid) {
        update(rs(cur), l, r, v);
    }
    else {
        update(ls(cur), l, mid, v);
        update(rs(cur), mid + 1, r, v);
    }
    //更新完子节点之后将自己也进行更新
    push_up(cur);
}
int query(int cur, int l, int r)
{
    if (tree[cur].l == l and tree[cur].r == r)
    {
        return tree[cur].sum;
    }
    //对子节点进行查询时,先将子节点值进行更新
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        return query(ls(cur), l, r);
    }
    else if (l > mid) {
        return query(rs(cur), l, r);
    }
    else {
        return query(ls(cur), l, mid) + query(rs(cur), mid + 1, r);
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("D:/VS CODE/C++/in.txt", "r", stdin);
        freopen("D:/VS CODE/C++/out.txt", "w", stdout);
    #endif
    cin >> n;
    build(1, 1, n);

    return 0;
}