线段树

原理

将一个区间和其所有不重叠的子区间分别存储到数组中，形成一个满二叉树，并且在线段树中每一个节点维护当前区间的值。

当某一个节点进行修改之后，需要修改当前节点和所有父节点。

当修改的是一个区间的值时，需要维护懒标记。懒标记代表当前节点的所有子节点应该加上的值，每次pushdown操作是将当前节点的懒标记推送到了子节点，并且将上次的操作真正的实际写到节点中。比如modify操作，pushdown之后所有子节点的值已经落实了修改，递归之后值完全正确，这时也要pushup更新父节点的值。总结上讲，当build和modify操作结束时，需要用pushup来更新当前节点值。当modify和query开始时，必须保证当前节点的值已经正确，因此需要用pushdown操作。

当查询某一个区间内的值时，只需要将包含在该区间内的所有最大区间的值进行计算即可得出，这一点和树状数组思想一致。

因此线段树可以进行单点和区间修改，区间查询。修改和查询的时间复杂度为O(logn)。

模板

//需要开4倍空间，最多有4n - 1个节点存在。
struct Node
{
    int l, r;
    int v;
}tr[N * 4];

//pushup操作，用子节点的信息计算父节点
void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

//可以对pushup再加一层封装，这样可以计算任意Node
void pushup(int u) {pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);}
void pushup(Node& u, Node& l, Node& r)
{
    u.sum = l.sum + r.sum;
    u.lsum = max(l.lsum, l.sum + r.lsum);
    u.rsum = max(r.rsum, r.sum + l.rsum);
    u.tsum = max({l.rsum + r.lsum, l.tsum, r.tsum});
}

//build操作，建立线段树，确定每个节点维护的区间
void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) return;

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

//单点修改操作，修改某一个叶子节点的值
void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = 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 (tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    int ret = 0;
    //否则找到树节点区间中点（因为要继续向下看看哪个区间能完全被包含）
    int mid = tr[u].l + tr[u].r >> 1;
    //如果l在mid左边，则说明向下一层的节点中有部分在当前查找区间中，递归
    if (l <= mid) ret = query(u << 1, l, r);
    //如果r在mid右边，也是需要再向下查找
    if (r > mid) ret = max(ret, query(u << 1 | 1, l, r));

    return ret;
}

//懒标记的pushdown操作
void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.sum += (left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

//使用懒标记修改区间的值
void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else
    {
        //开始之前保证当前u节点如果带有懒标记，一定计算完毕子节点，且将懒标记传递给子节点
        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);
    }
}