关于线段树我之前就写过博客也转载过他人的博客来介绍线段树。

递归版线段树：https://blog.csdn.net/hpu2022/article/details/81946151

非递归版线段树：https://blog.csdn.net/hpu2022/article/details/81946200

我自己以前写过的线段树模板：https://blog.csdn.net/hpu2022/article/details/81913776

YouTube上黄浩杰关于线段树的视频（感觉还不错）：

https://www.youtube.com/watch?v=e_bK-dgPvfM

这次又重学了一遍线段树，下面是重新总结的模板、

主要内容是：建树，单点更新，区间更新，区间查询，lazy标记

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

using namespace std;
const int N = 1010;
#define ls node*2 + 1    // 左儿子
#define rs node*2 + 2    // 右儿子

int tree[N*4], lazy[N*4];   // 线段树和懒标记
int a[N], n;    // 数组元素和个数

// 这里只是把建树递归后的操作提取出来做成一个函数
// node表示当前结点的编号
void push_up(int node) 
{
    tree[node] = tree[ls] + tree[rs];
}

// 建树 start end是原始数组的区间范围
void build(int start, int end, int node)
{
    if(start == end)
    {
        tree[node] = a[start];
        return;
    }
    int mid = (start + end) / 2;
    build(start, mid, ls);
    build(mid+1, end, rs);
    push_up(node);   // 左右子树建好以后就可以求当前节点的值了
}

// 单点更新 a[idx] = val;
// 带node是线段树的下标，node是当前线段树的当前所在节点的编号
void update(int idx, int val, int start, int end, int node)
{
    if(start == end)
    {
        tree[node] = val;  // 修改树中的节点
        a[idx] = val;  // 修改原始数组
        return;
    }
    int mid = (start + end) / 2;
    // 如果需要修改的点再左分支
    if(start <= idx && idx <= mid)
        update(idx, val, start, mid, ls);
    else
        update(idx, val, mid+1, end, rs);
    push_up(node);
}

// node表示当前节点，ln,rn分别表示左右子树的节点数量
void push_down(int node, int ln, int rn)
{
    if(lazy[node])
    {
        lazy[ls] += lazy[node]; // 下推标记
        lazy[rs] += lazy[node];
        tree[ls] += lazy[node] * ln;     // 修改子节点的Sum使之与对应的lazy相对应
        tree[rs] += lazy[node] * rn;
        lazy[node] = 0;    // 清除本结点标记
    }
}

// 区间更新
// L R表示操作区间，start, end表示当前节点区间，node是当前节点编号
void update2(int L, int R, int val, int start, int end, int node)
{
    if(L <= start && end <= R)
    {
        tree[node] += val * (end - start + 1);// 更新数字和，向上保持正确
        lazy[node] += val;// 增加lazy标记，表示本区间的Sum正确，子区间的Sum仍需要根据lazy的值来调整
        return;
    }
    int mid = (start + end) / 2;
    push_down(node, mid - start + 1, end - mid);
    if(L <= mid)    // 这里判断左右子树跟[L,R]有无交集，有交集才递归
        update2(L, R, val, start, mid, ls);
    if(R > mid)
        update2(L, R, val, mid+1, end, rs);
    push_up(node);
}

// 区间查询
// L, R表示查询区间，start, end表示当前节点区间，node表示当前节点编号
int query(int L, int R, int start, int end, int node)
{
    if(R < start || L > end)    // 没有交集
        return 0;
    else if(start == end)   // 区间缩小到1时
        return tree[node];
    else if(start <= L && R >= end) // 完全在区间内
        return tree[node];
    int mid = (start + end) / 2;

    push_down(node, mid - start + 1, end - mid);
    int ans = 0;
    ans += query(L, R, start, mid, ls);
    ans += query(L, R, mid+1, end, rs);
    return ans;
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
        }
        build(0, n-1, 0);
        // update(4, 6, 0, n-1, 0);
        printf("\n");
        for(int i=0; i<n*2+2; i++)
        {
            printf("tree[%d] = %d\n", i, tree[i]);
        }
        printf("\n");
        update2(0, 2, 3, 0, n-1, 0);
        for(int i=0; i<n*2+2; i++)
        {
            printf("tree[%d] = %d\n", i, tree[i]);
        }
        int ans = query(0, 1, 0, n-1, 0);
        printf("%d\n", ans);
         for(int i=0; i<n*2+2; i++)
        {
            printf("tree[%d] = %d\n", i, tree[i]);
        }
    }


    return 0;
}