线段树的功能：
1、区间查询
2、单点修改
3、区间修改->懒标记pushdown

pushup放在build和modify的后面
pushdown放在modify和query的前面

int w[N];   //N为所需的节点数，即为叶节点数

struct Node
{
    int l, r;
    int sum, add...
    //sum:当前区间的总和
    //add:懒标记，给以当前节点为根的每一个子树中的每一个节点加上add（不包含根节点）
}tr[N * 4]; //4 * N为整个线段树的节点数

//用两个子节点信息来计算父节点的信息
void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.v = max(l.v, r.v);
    ...
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

//懒标记 
void pushdown(Node &u, Node &l, Node &r)
{
    if (u.add)
    {
        l.add += u.add, l.sum += (LL)(l.r - l.l + 1) * u.add;
        r.add += u.add, r.sum += (LL)(r.r - l.l + 1) * u.add;
        u.add = 0;
    }
}

void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

//建树
void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0...};
    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 >= l && tr[u].r <= r)
    {
        tr[u].sum = ...
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

//区间修改
void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d; //
        ...
    }
    else    // 一定要分裂
    {
        pushdown(u);    //
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

//查询区间
//如果有多个要返回的值就返回Node，返回单个int也可以
//版本1
Node query(int u, int l, int r) 
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];

    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) query(u << 1, l, r)相关操作;
    if (l > mid) query(u << 1 | 1, l, r)相关操作;
    else    //
    {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        Node res;
        pushup(res, left, right);
        return res;
    }
    return ...;
}

//版本二
Node query(int u, int l, int r) 
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];

    pushdown(u);    //
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) query(u << 1, l, r)相关操作;
    if (r > mid) query(u << 1 | 1, l, r)相关操作;
    return ...;
}