Lintcode---线段树修改
修改 --- 线段 lintcode
2023-09-14 08:58:39 时间
样例
对于线段树:
[1, 4, max=3]
/ \
[1, 2, max=2] [3, 4, max=3]
/ \ / \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]
如果调用 modify(root, 2, 4)
, 返回:
[1, 4, max=4]
/ \
[1, 2, max=4] [3, 4, max=3]
/ \ / \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]
或 调用 modify(root, 4, 0)
, 返回:
[1, 4, max=2]
/ \
[1, 2, max=2] [3, 4, max=0]
/ \ / \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]
思路:首先清楚最大线段树的定义,然后,还是利用线段树的性质,分析清楚基准情形,利用递归来求解。
使用递归,虽然速度慢了些,但对于复杂问题,理解起来更容易,思路更清晰。
先找到index所在叶子节点,并修改该叶子节点的值,然后再从下往上依次更新其父节点的max值。
/** * Definition of SegmentTreeNode: * class SegmentTreeNode { * public: * int start, end, max; * SegmentTreeNode *left, *right; * SegmentTreeNode(int start, int end, int max) { * this->start = start; * this->end = end; * this->max = max; * this->left = this->right = NULL; * } * } */ class Solution { public: /** *@param root, index, value: The root of segment tree and *@ change the node's value with [index, index] to the new given value *@return: void */ /* 思路:首先清楚最大线段树的定义,然后,还是利用线段树的性质,分析清楚基准情形, 利用递归来求解。 使用递归,虽然速度慢了些,但对于复杂问题,理解起来更容易,思路更清晰。 先找到index所在叶子节点,并修改该叶子节点的值,然后再从下往上依次更新其父节点的max。 */ void modify(SegmentTreeNode *root, int index, int value) { // write your code here if(root==NULL){ return; } if(index>root->end||index<root->start){ return; } if(index==root->start&&root->start==root->end){ root->max=value; return; } modify(root->left,index,value); modify(root->right,index,value); root->max=max(root->left->max,root->right->max); } };
相关文章
- 黑苹果教程 - 修改分辨率最简单方法
- Linux中chmod -R 递归修改文件权限的操作和 默认权限umask
- 在 Vue 中,子组件为何不可以修改父组件传递的 Prop
- Greenplum修改hostname
- 一文学会如何下载、修改和续证PMP项目管理证书
- 【Android 文件管理】分区存储 ( 修改与删除图片文件 )
- mysql实现批量修改字段null值改为空字符串
- 运行参数Linux 下修改 Java 运行参数的指南(linux修改java)
- 解决Linux下时间变化问题:修改时间命令(linux修改时间命令)
- Linux修改静态IP地址:一步一步指南(linux修改静态ip)
- MySQL修改Host的操作技巧(mysql 修改host)
- 激活华为云,修改Redis网段路径(华为云更改redis网段)
- MySQL主键值不可修改(mysql不能修改主键值)
- Android在高jar包版本的工程中修改方法
- MSSQL监控数据库的DDL操作(创建,修改,删除存储过程,创建,修改,删除表等)
- jQuery修改li下的样式以及li下的img的src的值的方法