The structure of Segment Tree is a binary tree which each node has two attributes startand end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
- The root's start and end is given by
buildmethod. - The left child of node A has
start=A.left, end=(A.left + A.right) / 2. - The right child of node A has
start=(A.left + A.right) / 2 + 1, end=A.right. - if start equals to end, there will be no children for this node.
Implement a build method with a given array, so that we can create a corresponding segment tree with every node value represent the corresponding interval max value in the array, return the root of this segment tree.
Segment Tree (a.k.a Interval Tree) is an advanced data structure which can support queries like:
- which of these intervals contain a given point
- which of these points are in a given interval
See wiki:
Segment Tree
Interval Tree
Given [3,2,1,4]. The segment tree will be:
[0, 3] (max = 4)
/ \
[0, 1] (max = 3) [2, 3] (max = 4)
/ \ / \
[0, 0](max = 3) [1, 1](max = 2)[2, 2](max = 1) [3, 3] (max = 4)这道题是之前那道Segment Tree Build的拓展，这里面给线段树又增添了一个max变量，然后让我们用一个数组取初始化线段树，其中每个节点的max为该节点start和end代表的数组的坐标区域中的最大值。建树的方法跟之前那道没有什么区别，都是用递归来建立，不同的地方就是在于处理max的时候，如果start小于end，说明该节点还可以继续往下分为左右子节点，那么当前节点的max就是其左右子节点的max的较大值，如果start等于end，说明该节点已经不能继续分了，那么max赋为A[left]即可，参见代码如下：
class Solution { public: /** *@param A: a list of integer *@return: The root of Segment Tree */ SegmentTreeNode * build(vector<int>& A) { return build(A, 0, A.size() - 1); } SegmentTreeNode* build(vector<int>& A, int start, int end) { if (start > end) return NULL; SegmentTreeNode *node = new SegmentTreeNode(start, end); if (start < end) { node->left = build(A, start, (start + end) / 2); node->right = build(A, (start + end) / 2 + 1, end); node->max = max(node->left->max, node->right->max); } else { node->max = A[start]; } return node; } };
本文转自博客园Grandyang的博客，原文链接：建立线段树之二[LintCode] Segment Tree Build II ，如需转载请自行联系原博主。
