要想进行区间查询，我们可以使用前缀和。要想处理区间修改，我们可以使用差分。然而，如果我们需要同时进行区间查询与修改，这两种算法都无法高效地解决问题。
此时，我们就需要一种数据结构——线段树来帮助我们，它可以以 O(logn)\mathcal{O}(\log n)O(logn) 的时间复杂度处理这两种操作。
约定
本文中的代码仅作为示范，请根据题目实际情况选择合适的数据类型与数组大小。
简介
线段树是一种专门用来处理区间问题的数据结构，一般是完全二叉树。它基于分治思想将原序列递归地进行划分，处理并记录各个子区间的信息。查询时，我们将目标区间分解为 O(logn)\mathcal{O}(\log n)O(logn) 个子区间，将子区间中的信息整合起来，就得到了目标区间的信息。
线段树一般占用 O(n)\mathcal{O}(n)O(n) 的空间，实际多开 4n4n4n 大小，具体原因见 OI-Wiki。
由于目标区间由子区间的信息组合而成，线段树通常只用于维护符合结合律的操作。
建树
以维护区间和为例，我们首先需要建立线段树。可以考虑先从顶部出发向下直到底部，然后递归自底向上地建树。
首先，我们定义结构体node。
里面的data就是该节点存储的数据，lazy的含义之后会讲。
接下来为了简洁，我们实现一个函数pushup(idx)，它通过其子节点的信息维护当前节点的信息。
函数中，idx<<1是左孩子，idx<<1|1是右孩子。由于左移之后二进制的个位肯定是 000，我们将idx<<1按位或 111 其实就相当于将其加上一。
然后，我们实现建树函数build(l,r,idx)。如果区间的长度为 111，就表明已经到了最底层，将信息直接写入（即构建叶子节点）并开始返回。否则，递归到左右两侧的子树中，待两侧子树构建完毕再维护当前节点。
建树的操作是 O(n)\mathcal{O}(n)O(n) 的。在构建线段树时，我们通常这样调用它。
此时，idx中填写的就是根节点的编号，也就是 111。如果你实现了以 000 为根节点编号的线段树，你就应该调用build(0,n-1,0)，但并不推荐这样做。
更新
我们首先实现更新，不过区间更新操作是有很多种类型的，我们这里先假设更新就是给区间 [L,R][L,R][L,R] 中的每个元素加上 kkk。对于当前的区间 [l,r][l,r][l,r]，我们有三种情况。
1. [l,r]∩[L,R]=∅[l,r]\cap [L,R]=\varnothing[l,r]∩[L,R]=∅，即当前区间不与被修改区间相交。
2. [l,r]⊆[L,R][l,r]⊆[L,R][l,r]⊆[L,R]，即当前区间被修改的区间完全包含。
3. [l,r]∩[L,R]≠∅[l,r]\cap [L,R]\neq\varnothing[l,r]∩[L,R]=∅ 且 [l,r]⊈[L,R][l,r]\not\subseteq [L,R][l,r]⊆[L,R]，即当前区间与被修改区间相交但不被完全包含。
对于第一种情况，我们直接返回就行了，不需要执行任何操作。第二种情况，如果更新到了叶子节点，我们就对其进行更新并返回，否则继续递归，不然下面的节点没有更新到，会出现数据不一致。最后一种情况，我们也继续递归，并在递归完成后进行pushup()操作。
查询
实现了建树与更新后，我们处理查询。我们需要实现query(L,R,l,r,idx)，它负责查询目标区间 [L,R][L,R][L,R] 的信息。
同样有三种情况，这里不再列出。对于第一种情况，我们返回一个对结果无影响的值，这里是 000（因为 000 对区间和没有影响。如果是维护区间最大值，可以返回INT_MIN等）。第二种情况，我们直接返回当前节点的信息。最后一种情况，我们进行递归，将递归函数返回的值相加并返回。
懒惰标记
我们成功实现了一棵线段树。然而，它的效率并不如预期，没有通过 P3372。
我们发现在更新时，当前的代码会直接更新到叶子节点。然而，底部的一些节点在之后的查询中可能并没有被访问，这不就白更新了吗？这下，我们在结构体中声明的lazy就有用了。我们可以将修改操作的变化值存储在lazy中，只在必要时才将lazy下发给子节点并真正更新当前节点。由于这可以说是“懒得更新之后的节点”，它被称为懒惰标记。
我们首先实现pushdown(idx,l,r)，它负责处理当前节点的懒惰标记，并将其下发到子节点。
为什么还要传入当前区间呢？很简单，因为懒惰标记中存储的是区间中每个元素的增量，必须乘上区间长度才能得到区间增量。
接下来，我们在处理查询与更新操作时，如果需要向下递归，先pushdown()即可处理懒惰标记。然后，对于更新操作中的第二种情况，我们可以高效地解决而不必再继续递归。
到此，我们成功写出了一棵线段树。
不同类型的区间更新
除了全都加上 kkk，还有许多其他常见的区间更新方式。
区间乘法
如果我们的修改操作是将区间中的元素乘上 kkk，相应的处理就需要改变。不过单纯的区间乘法很简单，只需要注意两点。
1. 必须将lazy初始化为 111。
2. 在update()、pushdown()时直接乘上 kkk 就行了，区间乘法的更新对区间长度并没有需求。
代码就不放了，很简单。
直接修改
如果修改操作直接将区间中的元素修改为 kkk，我们可以让懒惰标记直接表示当前需要修改的值。不过这会导致无法通过将懒惰标记设为诸如 000 的值来表明没有操作。所以，我们可以额外在结构体中定义一个bool变量来表示当前节点是否有待更新的懒惰标记。
相应的pushdown()函数如下。
update()函数同理，就不放出来了。
混合修改
在 P3373 中，我们需要同时处理区间加、乘法并对某个模数取模。我们可以给加法、乘法各开一个单独的懒惰标记。
不过这会导致一个问题——在下传懒惰标记时，是先处理加法还是乘法的懒惰标记呢？
不妨设 mulx\text{mul}_xmulx 表示节点 xxx 的乘法懒惰标记，addx\text{add}_xaddx 表示节点 xxx 的加法懒惰标记，datax\text{data}_{x}datax 表示节点 xxx 当前维护的区间和。我们先看当前节点 xxx 的左孩子。如果先加后乘，新的 data2x\text{data}_{2x}data2x 就会变成
mulx[mul2x(data2x+add2x)+addx]=mulx(mul2xdata2x+mul2xadd2x+addx)=mulxmul2xdata2x+mulxmul2xadd2x+mulxaddx=mulxmul2x(data2x+add2x+addxmul2x)\begin{aligned} &\text{mul}_x[\text{mul}_{2x}(\text{data}_{2x}+\text{add}_{2x})+\text{add}_x]\\
&=\text{mul}_x(\text{mul}_{2x}\text{data}_{2x}+\text{mul}_{2x}\text{add}_{2x}+\text{add}_x)\\ &=\text{mul}_x\text{mul}_{2x}\text{data}_{2x}+\text{mul}_x\text{mul}_{2x}\text{add}_{2x}+\text{mul}_x\text{add}_x\\
&=\text{mul}_x\text{mul}_{2x}(\text{data}_{2x}+\text{add}_{2x}+\frac{\text{add}_x}{\text{mul}_{2x}}) \end{aligned} mulx [mul2x (data2x +add2x )+addx ]=mulx (mul2x data2x +mul2x add2x +addx )=mulx mul2x data2x +mulx mul2x add2x +mulx addx =mulx mul2x (data2x +add2x +mul2x addx )
所以，新的 add2x\text{add}_{2x}add2x 会变成 add2x+addxmul2x\text{add}_{2x}+\frac{\text{add}_x}{\text{mul}_{2x}}add2x +mul2x addx 。这是不可取的，因为它涉及除法，会出现精度丢失。我们必须先乘后加。
(data2xmul2x+add2x)mulx+addxlen=data2x(mul2xmulx)+(add2xmulx+addxlen)\begin{aligned} &(\text{data}_{2x}\text{mul}_{2x}+\text{add}_{2x})\text{mul}_x+\text{add}_x\text{len}\\ &=\text{data}_{2x}(\text{mul}_{2x}\text{mul}_x)+(\text{add}_{2x}\text{mul}_x+\text{add}_x\text{len}) \end{aligned} (data2x
mul2x +add2x )mulx +addx len=data2x (mul2x mulx )+(add2x mulx +addx len)
其中 len\text{len}len 表示当前区间长度。
也就是说，新的 mul2x\text{mul}_{2x}mul2x 是 mul2xmulx\text{mul}_{2x}\text{mul}_xmul2x mulx ，新的 add2x\text{add}_{2x}add2x 是 add2xmulx+addx\text{add}_{2x}\text{mul}_x+\text{add}_xadd2x mulx +addx ，完全可以。注意，这里 addx\text{add}_xaddx 并没有乘上 len\text{len}len，因为它表示的是区间中每个元素的待加量，而不是整个区间的。
当然，在pushdown()里，处理乘法、加法懒惰标记的代码顺序没有什么关系。
在区间乘法更新时，我们只需要给区间中的数据以及加法、乘法懒惰标记都乘上 kkk 就行了。
动态开点线段树
我们知道，线段树进行一次更新操作的时间复杂度是 O(logn)\mathcal{O}(\log n)O(logn)，也就是最多访问到 O(logn)\mathcal{O}(\log n)O(logn) 个节点。不妨设有 mmm 次操作，则实际最多访问到的节点数量为 O(mlogn)\mathcal{O}(m\log n)O(mlogn)，其余的节点就没有必要建出来了。像这样只建立被访问到的节点的线段树，称为动态开点线段树。
不过这样就会导致我们无法用 2n2n2n 与 2n+12n+12n+1 来表示左右孩子，因此我们必须在结构体中对其进行记录。如果没有左右孩子，用 000 表示。
由于需要动态开点，原本的build()已经不再适用。现在，对于每个新的输入，我们都进行一次单点更新。这样做的时间复杂度是 O(nlogn)\mathcal{O}(n\log n)O(nlogn)。如果你采用和普通线段树一样的建树方式，最后就会把整棵树全都建出来，也就失去了动态开点的意义。
每次进行pushdown()操作时，我们都检查当前节点的子节点。如果没有，就创建它。其他的地方，动态开点线段树则几乎与普通线段树别无二致。
标记永久化
在前面，我们采用pushdown()对懒惰标记进行下传。但对于懒惰标记的处理，实际上还有另一种方法——标记永久化。相比于下传的方法，标记永久化的常数会更小。如它的名字，懒惰标记一旦打上就再也不会消失，而是在查询与更新操作中直接计算。
更具体的，在标记永久化中，我们不再进行pushdown()操作。我们依旧有之前的三种情况。对于情况二，就表明当前区间内所有子节点都受到了修改，可以直接打上懒惰标记，修改data并返回。对于情况三，只有一部分节点需要修改，我们不能直接修改当前节点的懒惰标记，于是只能修改data，并继续向下递归处理子节点。
查询时，我们需要累加路径上所有节点的懒惰标记，才能计算出当前区间的真实值。
