Lintcode: Segment Tree Query
Tree Query SEGMENT lintcode
2023-09-11 14:14:07 时间
For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end). Design a query method with three parameters root, start and end, find the maximum number in the interval [start, end] by the given root of segment tree. Have you met this question in a real interview? Yes Example For array [1, 4, 2, 3], the corresponding Segment Tree is: [0, 3, max=4] / \ [0,1,max=4] [2,3,max=3] / \ / \ [0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3] query(root, 1, 1), return 4 query(root, 1, 2), return 4 query(root, 2, 3), return 3 query(root, 0, 2), return 4
这道题的启示是:Segment Tree 不光是可以找线段和,还可以找线段max, min等各种各样的指标
1 /** 2 * Definition of SegmentTreeNode: 3 * public class SegmentTreeNode { 4 * public int start, end, max; 5 * public SegmentTreeNode left, right; 6 * public SegmentTreeNode(int start, int end, int max) { 7 * this.start = start; 8 * this.end = end; 9 * this.max = max 10 * this.left = this.right = null; 11 * } 12 * } 13 */ 14 public class Solution { 15 /** 16 *@param root, start, end: The root of segment tree and 17 * an segment / interval 18 *@return: The maximum number in the interval [start, end] 19 */ 20 public int query(SegmentTreeNode root, int start, int end) { 21 // write your code here 22 if (root.start==start && root.end==end) return root.max; 23 int mid = (root.start+root.end)/2; 24 if (end <= mid) return query(root.left, start, end); 25 else if (start > mid) return query(root.right, start, end); 26 else return Math.max(query(root.left, start, mid), query(root.right, mid+1, end)); 27 } 28 }
相关文章
- Java实现LeetCode 110. Balanced Binary Tree
- [Algorithm] Check if a binary tree is binary search tree or not
- [MST] Attach Behavior to mobx-state-tree Models Using Actions
- LeetCode:144_Binary Tree Preorder Traversal | 二叉树的前序遍历 | Medium
- [LeetCode] Count Complete Tree Nodes
- SAP Spartacus里unit list tree的页面显示和后台响应数据的对应关系
- Atitit 数据结构与常见文件元数据结构 目录 1. 分类 内部数据结构与外部存储数据结构1 2. 编程语言内部数据结构 (堆栈 树 图等1 2.1. 数据结构 (集合,列表,tree,map
- XAI之SHAP:可解释性之SHAP值的公式推导(基于原论文利用树类模型的Tree SHAP公式推导)之详细攻略
- tree 树形递归修改 key
- Error pulling origin: error: The following untracked working tree files would be overwritten by...
- PAT 1099 Build A Binary Search Tree[BST性质]
- PAT 1110 Complete Binary Tree C++ 版
- PAT 1151 LCA in a Binary Tree C++版
- Tree-shaking的作用
- Device Tree 设备树 背景介绍