原来说要写线段树的，但是普通线段树还是比较容易理解的，个人感觉比树状数组要好理解，再加上我只会普通线段树，所以暂时就不对线段树详细讲解了。不过下面还是简单介绍一下完事。
基本思想
概述
简单来说，线段树就是一棵完全二叉树，其中每个节点维护了一段区间的信息。每个非叶子节点维护的区间长度一定大于1，否则它就是叶子节点。线段树的深度为$log(n)$。在修改和查询时，需要从根结点开始向下遍历，最多需要访问$log(n)$个节点，因此线段树的修改和查询操作都是$log(n)$复杂度的。
懒标记
当我们当前遍历的节点所维护的整个区间都要进行修改操作时，如果我们还是修改其子节点，那么时间开销是巨大的。因此当我们遇到这种情况时，就给这个节点打上一个懒标记，同时对应地修改该节点的值。查询时，如果需要访问子节点，则需要保证懒标记一定被下传到了子节点那里，不然懒标记就没有用了。
但懒标记也不是万能的，比如我们对一段区间进行开方操作，区间内每个数都要开方(同时下取整)，那么我们打懒标记就是错误的。原因在于：加法操作满足结合律，对区间内每个数进行操作，就相当于对整个区间和进行操作。而开方操作没有这种性质，即对区间内每个元素进行操作不等于对整个区间和开方。解决方法就是暴力修改，区间开方时我们直接修改每个叶子节点并重新统计区间和。这个区间开方操作在洛咕也有对应的题，链接：P4145
线段树与树状数组的比较
- 线段树可以做一些树状数组做不到的操作，比如区间查询最值。其实我们了解树状数组的原理后，可以发现树状数组查询区间信息就是利用前缀和的思想，因此前缀和能做到的树状数组基本都能做到。所以说，在通用性上，线段树要优于树状数组。
- 在编程复杂度上，线段树的码量要远远大于树状数组，因此，写线段树时要是不小心写出点bug，调试时要比树状数组困难一些。
- 两者的修改查询操作复杂度均为$log(n)$，但线段树的常数要大一些。
注意事项
当线段树上的节点有多种懒标记时，一定要注意正确处理不同种类懒标记之间的关系。
例如我们需要让线段树同时支持区间乘法和区间加法两种操作，则线段树上就要有加法标记和乘法标记，那么我们在给一个节点打上乘法标记时，这个节点的加法标记也要对应地修改，否则喜提WA一份。