自己yy的定义：将一个区间$[l, r]$以$[l, \ mid]$和$[mid + 1, \ r]$细分下去，直到$l==r$，每一个区间用结构体struct维护

struct Node
{
    int l, r;  // 区间的左右端点
    int sum;  // 区间[l, r]内的和
    ...  // 看自己还需要维护什么元素
}

存储方式：类似于堆的存储方式，用数组来映射。

$ {对于某个点x} \left\\{ \begin{aligned} 父节点：& \lfloor{ \frac x 2}\rfloor \ \ 或者 \ \ x >> 1 \\\ 右儿子：& 2x \ \ 或者 \ \ x << 1 \\\ 右儿子：& 2x + 1 \ \ 或者 \ \ x << 1 \ | \ 1 \\\ \end{aligned} \right. $

结构体数组开多少：$4n$

区间细分图如下：

$$(_1-------------------------------------_7)$$

$$(_1------------------_4)(_5-----------------_7)$$

$$(_1--------_2)(_3---------_4)(_5-------_6)(_7--------_7)$$

$$(_1----_1)(_2----_2)(_3----_3)(_4----_4)(_5----_5)(_6----_6)(_7----_7)$$

介绍线段树中一些重要的函数

①：pushdown

带懒标记的线段树中使用，以后再补充: )

②：pushup

作用：用子节点信息更新当前节点信息

代码：

// 用子节点更新父节点的信息，不一定是区间和，有可能是其他的信息
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;  // u << 1 | 1 == u * 2 + 1;
}

③：build

作用：在一段区间上初始化线段树

代码：

void build(int u, int l, int r)  // u：当前节点，l：初始化的左区间，r：初始化的右区间
{
    if(l == r) tr[u] = {l, r, w[r]};  // w[r] == w[l] (r == l)
    else
    {
        tr[u] = {l, r};  // 初始化
        int mid = l + r >> 1;
        // 递归处理[l, mid], [mid + 1, r]
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);  // 用跟新后的值求和
    }
}

④：modify

作用：修改

代码：

void modify(int u, int x, int v)  // u：当前节点，x：修改的点，v：修改的值
{
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);  // 要修改的区间在[l, mid]中
        else modify(u << 1 | 1, x, v);  // 要修改的区间在[mid + 1, r]中
        pushup(u);
    }
}

⑤：query

作用：查询

代码：

int query(int u, int l, int r)  // u：当前节点，l：查询的左区间，r：查询的右区间
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;  // 当前区间已经包含了u的区间
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if(l <= mid) sum = query(u << 1, l, r);
    if(r > mid) sum += query(u << 1 | 1, l, r);  // 为什么不取=？ 因为r == mid + 1
    return sum;
}

习题：动态求连续区间和
写完思路，做题又花了1h

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

using namespace std;

const int N = 100010, M = 4 * N;

struct Node
{
    int l, r, s;
}tr[M];
int n, m;
int a[N];

void pushup(int u)
{
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, a[r]};
    else
    {
        tr[u] = {l, r};  // 记得初始化
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if(tr[u].l == tr[u].r) tr[u].s += v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].s;  // 查询区间包含住了当前的区间

    int sum = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) sum = query(u << 1, l, r);  // [l, mid]
    if(r > mid) sum += query(u << 1 | 1, l, r);  // [mid + 1, r]
    return sum;
}

void dfs(int u)  // 出问题了可以参考这个调试一下
{
    if(tr[u].l == tr[u].r) cout << "* " << tr[u].l << " " << tr[u].r << " " << tr[u].s << endl;
    else
    {
        cout << tr[u].l << " " << tr[u].r << " " << tr[u].s << endl;
        dfs(u << 1), dfs(u << 1 | 1);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    build(1, 1, n);

    // dfs(1);

    while(m -- )
    {
        int c, a, b;
        scanf("%d%d%d", &c, &a, &b);
        if(c == 0) printf("%d\n", query(1, a, b));
        else modify(1, a, b);
    }

    return 0;
}