【模板】线段树1

题目

洛谷P3374

题解

线段树的结构与树状数组相似,但线段树更加通用,维护的数据只要满足区间加即可。线段树是一棵二叉树,每个节点表示一个区间。假设某个节点表示[l,r],mid=(l+r)/2,则它的左子节点表示[l,mid],右子节点表示[mid+1,r]。若一个节点的编号为x,则它的左子节点编号为x*2,右子节点编号为x*2+1。存储节点的数组大小,通常为数据量的4倍。

线段树的单点修改操作,只要将包含被修改元素的节点全部更新即可。

线段树的区间查询操作,只要一直递归,看当前节点表示的区间是否包含于被查区间,如果不是,再看被查区间是否与左/右子节点表示的区间有重合部分。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月31日 下午8:02

好!!!