标签： 线段树

5 篇文章

[NOI2015]软件包管理器[树链剖分,线段树]
|
969
|
0
|
算法,软
题面 毒瘤数据结构复习系列. 设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1 卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0 线段树的区间覆盖只要把懒标记的+=改为=就行了 看到题解中还有一种更妙的做法: 只进行update操作, 统计线段树根节点sum值变化即可, 理论上常数是…
树树链剖分线段树
[洛谷P4513]小白逛公园[线段树]
|
1,004
|
0
|
算法,软
题面 双倍经验: https://www.luogu.org/problem/SP1716 复习一下线段树, 老是写挂... 这道题是一种常见线段树处理连续子段问题的做法. 每个节点维护区间最大子段和, 从左端点开始的最大子段和, 从右端点开始的最大子段和, 区间和. 这样合并两个节点时就可以考虑以下几种情况: 对于合并后的从左端点开始的最大子段和…
树线段树
[洛谷P3384]【模板】树链剖分
|
842
|
0
|
算法,软
复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长... 考虑如何把一棵树通过编号处理成尽量少的链, 同时保证每棵子树/每条链的编号都连续. 容易发现dfs序就满足前者, 这样就保证了每棵子树都在一个连续区…
树树剖模板线段树