[TOC]
区间问题
区间查询
区间求和
略……
区间中位数
权值线段树，查找区间排名中间的数。
区间修改
区间加
懒惰标记，略……
区间乘
同区间加
区间加和乘
两个标记，tag_add和tag_mul。
- 区间乘x：tag_add *= mul, tag_mul += mul;
- 区间加x：tag_add += mul;
区间开方
题目的开放一般就是向下取整，因为一个数经过开放运算递减速度极快，经过几次运算后就为1了，因此可以直接对区间操作，不考虑全1区间。
区间位运算
区间位运算的思路就是把数字的每一位分别建立线段树，对于一个32位整型数建立32棵线段树即可，维护区间1的个数，查询时第 $i$ 棵树区间 $[l,r]$ 的贡献是 sum[l,r] *（1« i ）。之后根据具体情况做区间修改。
与（&）
区间[l,r]与x：把x每一位取出，若为0，对应线段树的[l,r]区间清0，不考虑全0区间；若为1，值不变，不做修该。
或（|）
区间[l,r]或x：把x每一位取出，若为1，对应线段树的[l,r]区间置1，不考虑全1区间；若为0，值不变，不做修该。
异或（^）
区间[l,r]异或x：把x每一位取出，若为1，修改对应树的标记 tag[rt] ^= 1，a[rt] = r-l+1-a[rt]。不考虑当前位是0的情况，因为0 ^ 0 = 0 , 1 ^ 0 = 1，值未发生改变。
区间合并
求区间 [l,r] 内最长连续相同子区间的长度。
多开三个数组 l、r、m，分别表示区间中从左到右、从右到左、总的最长连续相等子区间。上推和下推标记以及查询时需要仔细考虑。
例题详见：线段树合并