线段树乱写

一个常用的数据结构

线段树维护单调栈

例题:God Knows , 牛半仙的妹子序列..
亦可以看作是维护极长上升子序列..右边先行..

线段树区间查询

大多部分线段树均是查询\(tr[x].l\geq ql\ and\ tr[x].r\leq qr\)便停止。
但是有一部分题目并不是查询到这个条件就停止，
例如：矩形(noip模拟35)，一个比较明显的扫描线，
因为从未写过区间信息不满足时就停止下访，
于是便错误地合并了一些信息..
但是对于一些有特殊性质的题目，可以选择到达区间后，将区间信息下传给子区间，
然后再将子区间的答案统计一下，
这样的常数可能稍大，但并不是剧烈地影响时间复杂度..

另外不要写成： (一个过于低级的错误了..)

\[if(ql \leq mid)\ sum+=query(x<<1); \]

\[else\ return\ sum+=query(x<<1\ |\ 1); \]

第二行要写成：

\[if(qr>mid)\ sum+=query(x<<1\ |\ 1); \]

线段树区间合并信息

经典的一道题：山海经..
在更大的区间\(pushup\)即可..

线段树解决高维偏序问题

解决二维偏序问题，有些类似权值线段树，亦可使用树状数组解决..

解决三维偏序问题，可以选择CDQ分治，也可以选择使用树套树..
其实也并非全部都是真正意义上的树套树，亦可以将元素存储在区间节点上，同样是上面的的题目‘矩形‘，可以将三维偏序降低为二维偏序，而方法就是在节点上开了一个\(set\)维护..

线段树乱写

原文：https://www.cnblogs.com/AaMuXiiiiii/p/15130049.html