线段树学习笔记
发布日期: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].rr) 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月13日 17时11分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
华为100万部鸿蒙,2019年Q4发布 华为100万部鸿蒙OS手机已开测
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命令_易语言通过“打开”命令操作数据库
2019-04-21
mysql slave 1062_mysql主从同步slave错误1062
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