前言

前言

注意: 这个文章的你可以在 rbook_old.roj.ac.cn 上阅读老的版本，还没有迁移过来

线段树(sgt, segment tree).

sgt有两种写法,原始的写法类似堆,建立在完全二树上,节点$i$的左孩子为$2 \times i$

那些线段树能解决的问题

• 区间最值
• 区间和
• 有条件的和(CF600E: 有条件的和:最大数量的编号和)
• 无序序列里第一次出现小于$x$的位置

时间复杂度

线段树模板