线段树

总结线段树的五大操作： build（建树），modify（修改），query（查询），pushup（自底向上维护父子节点关系，类似于更新），pushdown（维护lazytag），方便日后查询。

pushup

一般不会太过复杂，主要维护父子节点的关系，根据题意维护即可。

void pushup(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
} // 父节点的区间和等于左右儿子的区间和。

void pushup(int u) {
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
} // 父节点的最大值等于左右儿子的最大值。

pushdown

pushdown操作主要是用于维护lazytag，表示下传lazytag。

主要分为三步

1.判断是否含有lazytag

2.令左右节点的值按照lazytag进行修改，并下传lazytag至左右节点

3.将当前节点的lazytag置空

注意：

1.我们此处lazytag的含义是当前节点含有lazytag，并且区间已经修改过，因此在下传时要先更新区间值。

2.lazytag的核心是延迟修改，所以只在modify和query操作完全包含区间时才不会下传，当不完全包含区间时，表示我们必须要向下寻找剩余的区间，那么再向下的区间就不得不修改，因此要先进行pushdown

void pushdown(int u) // 例为维护区间加的lazytag
{
    auto &r = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (r.add){
        left.add += r.add, left.sum += (left.r - left.l + 1) * r.add;
        right.add += r.add, right.sum += (right.r - right.l + 1) * r.add;
        r.add = 0;
    }
}

build

void build (int u, int l, int r) {
	if (l == r) tr[u] = {l, r, q[r]};
	else {
		tr[u] = {l, r, q[r], 0}; // 该节点的左端点，右端点，以及维护的值和lazytag（可以不为1）
		int mid = l + r >> 1;
		build(u << 1, l, mid); // 向左下递归建树
		build(u << 1 | 1, mid + 1, r); // 向右下递归建树
		pushup(u); // 最后自底向上更新节点所维护的值
	}
}

modify

单点修改

void modify(int u, int x, int v) // x为待修改的数的下标，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); // 修改后自底向上更新一下。
    }
}

区间修改

含lazytag操作的区间修改，我们需要首先判断：

1.如果当前节点的区间被完全包含在所找的区间内，那么不再继续向下寻找，更新当前节点的值，打上lazytag，到此为止。

2.如果不完全包含，那么先下传标记（如果有标记），再左右递归，直到完全包含（只有一个也算）。最后再向上更新。

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 {
		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);
	}
}

query

query操作就相对直白，分为以下几步

1.如果当前节点被完全包含查询区间时，那么直接返回节点值

2.否则就先下传lazytag，再递归左右儿子分别求和，要注意lr和tr[u].l, tr[u].r的区别。

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(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);
    return sum;
}