从2.10到2.17，线段树已经断断续续的刷了七天了。刷题计划是根据http://www.notonlysuccess.com/index.php/segment-tree-complete/comment-page-3/#comment-5250来的，不过只刷了相对代表性的题目。线段树的应用十分灵活，以后还要继续。这里写一写个人做题的总结，方便以后复习用。
总体上线段树的题目共分为4部分，单点更新，成段更新，区间合并和扫描线。
单点更新：是最基础的题目。更新到叶子节点pos，之后把信息再更新上来，即更新其父亲节点。
hdu 1166 敌兵布阵：单点增加或减少某值，区间求和。
hdu 1754 I Hate It :单点更新，区间求最值。
poj 2828 Buy Tickets :每个人都有自己的权值和他想插入的位置。输出队列最后状态，用权值表示。
逆序插入线段树，将权值插入到第pos个位置。每插入一个，区间长度减1.
hdu 1394 Minimum Inversion Number:求逆序对数。
增加一个域num,初始为0。每输入一个数x，其所在的区间计数器加1.询问[x+1,n]的num（区间求和），就是当前比x大的数。
poj 2886 Who Gets The Most Candies:线段树模拟约瑟夫环。
增加一个域len代表当前区间还有多少人。query()用来询问第k个出圈人的原始位置。
成段更新：
hdu 1689 Just a Hook :将某区间的价值更改为val（1,2,3）,并求总区间的和。
增加一个域col，初始化为1。当区间col为正时说明该区间价值均为col,为负值说明不止一种价值。更新区间[l,r]时，若当前区间没被完全覆盖并col为正，先将当前区间传递左右子树，并将自己区间置为-1，再递归左右子树。区间求和，根据区间col求。
poj 2528 Mayor's Posters:市长贴海报，给出每个海报的左右区间，问最后能看到多少张海报。
由于坐标范围太大，首先离散化，先对坐标不分左右排序，将其映射到1~n上，对[1,n]建树。增加一个域kind,kind>0表示被第kind个海报完全覆盖，kind = 0表示没有覆盖或不止一张覆盖。对区间成段更新时，若当前区间没有被待更新区间完全覆盖，首先将该区间的kind传递给左右子树，并将自己kind置为0。查找区间端点对应编号时二分。最后计数时简单哈希。
poj 2777 Count Color :给一个长度为L的棒涂色，询问某区间有几种颜色，初始色为1。
类似于贴海报。同样增加一个域kind,kind>0表示该区间是纯色，第kind种颜色。kind = 0表示该区间是混合色。对区间更新时，若当前区间没有被完全覆盖并且是纯色，先将该区间的kind传给左右子树，并将自己区间置为0，说明该区间已不是纯色，再递归更新。询问区间涂了多少种色时，就是根据kind值哈希。
poj 3468 A Simple Problem with Integers:给区间同时增加一个数，询问区间的和。
增加两个域sum,add,分别是该区间的和，该区间的公共增量。更新时，若当前区间完全被覆盖，直接加上来并记录add。否则，公共增量先向下传递，自己区间add置为0表示已经向下传递，同时左右子树的sum值也要根据公共增量改变。然后递归更新，最后再把信息更新上来。询问区间和时，同样的，必要时公共增量也要向下传递。
区间合并：通常询问满足条件的最长连续区间
poj 3367 Hotel: 1 a:询问是不是有连续长度为a的空房间，有则返回区间的最左端点。 2 a b 将[a,a+b-1]清空。
增加四个域lx,rx,ax,col,分别表示从左数连续空房间长度，从右数连续空房间长度，该区间中连续空房间最长长度，该区间住房状态。col>0全住满，col=0全空，col=-1有房间住。询问最长连续区间时包括三种，在左子树，右子树或中间。更新时，先向下传递col（col==0 或col==1），递归之后再把信息更新上来。
POJ 2892 Tunnel Warfare：n个连续的村庄，可以摧毁x村庄，可以修复x村庄，询问与x村庄直接或间接相连的村庄数。
单点更新和区间合并问题。增加三个域lx,rx,ax,分别表示从左数连续的村庄数，从右数连续的村庄数，区间内连续村庄的最大值。摧毁或修复x村庄是单点更新，切记更新后要把信息再更新到父节点。询问x所在区间连续最大值时，递归终止条件时该区间全空或全满。然后递归左右子树。
扫描线：求面积并，周长并等。
hdu 1542 Altantis:给每个矩形的左下坐标和右上坐标。求面积并。
矩形端点坐标太大且是double型，首先排序去重离散化。增加两个域，len,cnt分别表示节点被覆盖的长度和节点被覆盖的情况。len>0说明被完全覆盖，len=0说明未被完全覆盖，不会出现len<0。扫描前，先对矩形的边按高度从小到大排序。然后挨个扫描，每扫描一条边，也就是把这条边从总区间中加上或删去（根据这条边是矩形上边还是下边），就求现在总区间被覆盖的长度然后乘上这条线段和下一条线段的高度差。
暂且记录这些，还有待完善更新。