线段树学习笔记
发布日期:2021-07-22 07:28:56 浏览次数:2 分类:技术文章

本文共 2716 字,大约阅读时间需要 9 分钟。

参考资料:

1. https://zhuanlan.zhihu.com/p/34150142
2. https://www.cnblogs.com/jason2003/p/9676729.html

各操作代码实现:

class treenode {
public: int l; //线段左下标 int r; //线段右下标 int sum; //线段和 int lz; //标记位};treenode tree[100];void build(int i, int l, int r) {
//递归建树 tree[i].l = l; tree[i].r = r; if (l == r) {
//如果这个节点是叶子节点 tree[i].sum = 1; return; } int mid = (l + r) >> 1; build(i * 2, l, mid);//分别构造左子树和右子树 build(i * 2 + 1, mid + 1, r); tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;//刚才我们发现的性质return ;}int search(int i, int l, int r) {
if (tree[i].l >= l && tree[i].r <= r)//如果这个区间被完全包括在目标区间里面,直接返回这个区间的值 return tree[i].sum; if (tree[i].r
r) return 0;//如果这个区间和目标区间毫不相干,返回0 int s = 0; if (tree[i * 2].r >= l) s += search(i * 2, l, r);//如果这个区间的左儿子和目标区间又交集,那么搜索左儿子 if (tree[i * 2 + 1].l <= r) s += search(i * 2 + 1, l, r);//如果这个区间的右儿子和目标区间又交集,那么搜索右儿子 return s;}void add(int i, int dis, int k) {
//修改dis结点,加上一个k if (tree[i].l == tree[i].r) {
//如果是叶子节点,那么说明找到了 tree[i].sum += k; return; } if (dis <= tree[i * 2].r) add(i * 2, dis, k);//在哪往哪跑 else add(i * 2 + 1, dis, k); tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;//返回更新 return;}void add(int i, int l, int r, int k) {
//区间修改,把这个区间加上k,便于单点查询 if (tree[i].l >= l && tree[i].r <= r) {
//如果这个区间被完全包括在目标区间里面,讲这个区间标记k tree[i].sum += k; return; } if (tree[i * 2].r >= l) add(i * 2, l, r, k); if (tree[i * 2 + 1].l <= r) add(i * 2 + 1, l, r, k);}int ans = 0;void search(int i, int dis) {
//单点查询 ans += tree[i].sum;//一路加起来 if (tree[i].l == tree[i].r) return; if (dis <= tree[i * 2].r) search(i * 2, dis); if (dis >= tree[i * 2 + 1].l) search(i * 2 + 1, dis);}void addadv(int i, int l, int r, int k){
if (tree[i].r <= r && tree[i].l >= l)//如果当前区间被完全覆盖在目标区间里,讲这个区间的sum+k*(tree[i].r-tree[i].l+1) {
tree[i].sum += k * (tree[i].r - tree[i].l + 1); tree[i].lz += k;//记录lazytage return; } push_down(i);//向下传递 if (tree[i * 2].r >= l) addadv(i * 2, l, r, k); if (tree[i * 2 + 1].l <= r) addadv(i * 2 + 1, l, r, k); tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum; return;}void push_down(int i){
if (tree[i].lz != 0) {
tree[i * 2].lz += tree[i].lz;//左右儿子分别加上父亲的lz tree[i * 2 + 1].lz += tree[i].lz; int mid = (tree[i].l + tree[i].r) / 2; tree[i * 2].sum += tree[i].lz * (mid - tree[i * 2].l + 1);//左右分别求和加起来 tree[i * 2 + 1].sum += tree[i].lz * (tree[i * 2 + 1].r - mid); tree[i].lz = 0;//父亲lz归零 } return;}int searchadv(int i, int l, int r) {
if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum; if (tree[i].r
r) return 0; push_down(i); int s = 0; if (tree[i * 2].r >= l) s += searchadv(i * 2, l, r); if (tree[i * 2 + 1].l <= r) s += searchadv(i * 2 + 1, l, r); return s;}

转载地址:https://blog.csdn.net/m0_45689014/article/details/113758058 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:牛客网 KY6 手机键盘
下一篇:牛客网 KY108 Day of Week

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月13日 17时11分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

华为100万部鸿蒙,2019年Q4发布 华为100万部鸿蒙OS手机已开测 2019-04-21
android+大富翁+局域网,【图片】大富翁6局域网(LAN)多人联机教程(求精)_大富翁吧_百度贴吧... 2019-04-21
rn webview加载本地静态html,React Native - Webview 加载本地文件 2019-04-21
dax powerbi 生成表函数_Power BI |DAX函数のCALCULATETABLE、CALENDAR函数以及相关表生成函数... 2019-04-21
编程之类的文案_如何锻炼写文案的能力? 2019-04-21
vscode 不能使用中文输入法_vscode中vim插件设置 2019-04-21
当集合a为空集时a的取值范围_1.1.2 集合间的基本关系 2019-04-21
vue 可合并表格组件_Vue实战046:详解Mixins混入使用和注意事项 2019-04-21
python包怎么做双重差分did分析_多变量相关性分析(一个因变量与多个自变量) 2019-04-21
fi sap 凭证冲销 稅_SAP中的成本要素 2019-04-21
mysql幻读是什么意思_MySQL中的幻读,你真的理解吗? 2019-04-21
mysql执行计划中性能最差的是_MySQL性能优化(七):MySQL执行计划,真的很重要,来一起学习吧... 2019-04-21
易语言执行mysql命令_易语言通过“打开”命令操作数据库 2019-04-21
mysql slave 1062_mysql主从同步slave错误1062 2019-04-21
mysql构造器_MySQL行构造器表达式优化(Row Constructor Expression) 2019-04-21
2008日志清理 server sql_SQL Server 2008 清除日志 2019-04-21
mac mysql root 权限_Mac平台重新设置MySQL的root密码 2019-04-21
mysql新增一列_MySQL-ProxySQL中间件 2019-04-21
mysql 30入门_30分钟带你快速入门MySQL教程 2019-04-21
kangle主机怎么配置MySQL_kangle web服务+easypanel主机控制面板快速搭建网站和数据库以及管理空间详细教程... 2019-04-21