线段树算法

概括

线段树是一咱二叉搜索树,与区间树相似,它将一个区间划分成一些子区间,每个子区间对应线段树中的一个叶结点
线段树可以快速查找一个节点在若干条线段中出现的次数,时间复杂度$O(\log N)$,它还有一个空间优化：离散化

线段树资料线段树完全版 ~by NotOnlySuccess

• 文库
• 网盘下载

入门

想一想我们学习过的RMQ,RMQ是用来求区间最值问题的, 一次处理,n次查询.如果数据在查询的过程中改变了怎么办?

我们从一个简单的题目来入门线段树:

有一个数组aN+1,a[1]~a[N]里面的数字是变化的(1<= a[i]<=50)
接下来每行有一条命令，命令有4种形式：

• (1) Add i j,i和j为正整数,a[i]+=j（j不超过30）
• (2)Sub i j ,i和j为正整数,a[i]-=j（j不超过30;
• (3)Query i j ,i和j为正整数,i<=j，表示询问a[i]+a[i+1]+….a[j];

• (4)End 表示结束，这条命令在每组数据最后出现;

  sample input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

每组数据最多有40000条命令

单点更新

操作

• build() 建立
• update() 更新操作
• pushup(rt) 用孩子更新父亲
• pushdown(rt) 把当前结点信息给孩子结点
• query(l,r,rt) 查询区间信息
• maxn maxn<<2
• lson rson

build tree

成段更新

离散化

区间合并

poj3667

扫描线

多颗线段树问题

ZKW线段树

经典题目

• 投影
• 海报