# Segment Tree

Segment Tree(线段树)

1. 二叉树
2. 线段树的每个节点表示的是一段区间和最大值（或最小值）
3. 节点的左子树 = 父亲区间分裂后的左区间

1. 查询的区间 和 线段树节点表示的区间 相等 -》直接返回节点的最大值
2. 查询的区间 被 线段树节点表示的区间 包含 -》递归向下搜索左右子树
3. 查询的区间 和 线段树节点表示的区间 不相交 -》停止搜索子树
4. 查询的区间 和 线段树节点表示的区间 相交不相等 -》分裂查找左右子树 eg.max[1,3] = max([1,1], [2,3])

1. 自上而下递归分裂
2. 自下而上回溯更新

#### Segment Tree Query

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.

Example

For array `[1, 4, 2, 3]`, the corresponding Segment Tree is:

```<code>                  [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]
</code>```

query(root, 1, 1), return `4`

query(root, 1, 2), return `4`

query(root, 2, 3), return `3`

query(root, 0, 2), return `4`

Note

It is much easier to understand this problem if you finished Segment Tree Build first.

```public int query(SegmentTreeNode root, int start, int end) {
if (root == null) {
return -1;
}
if (root.start == start && root.end == end) {
return root.max;
}
int mid = root.start + (root.end - root.start) / 2;
int leftMax = Integer.MIN_VALUE;
int rightMax = Integer.MIN_VALUE;
if (start <= mid) {
if (end <= mid) {
leftMax = query(root.left, start, end);
} else {
leftMax = query(root.left, start, mid);
}
}
if (end > mid) {
if (start >= mid) {
rightMax = query(root.right, start, end);
} else {
rightMax = query(root.right, mid + 1, end);
}
}
return Math.max(leftMax, rightMax);
}```

Segment Tree Query II

For an array, we can build a `SegmentTree` for it, each node stores an extra attribute`count` to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)

Design a `query` method with three parameters `root`, `start` and `end`, find the number of elements in the in array’s interval [start, end] by the given root of value SegmentTree.

Example

For array `[0, 2, 3]`, the corresponding value Segment Tree is:

```<code>                     [0, 3, count=3]
/             \
[0,1,count=1]             [2,3,count=2]
/         \               /            \
[0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
</code>```

`query(1, 1)`, return `0`

`query(1, 2)`, return `1`

`query(2, 3)`, return `2`

`query(0, 2)`, return `2`

Note

It is much easier to understand this problem if you finished Segment Tree Build and Segment Tree Query first.

```public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > root.end || end < root.start) {
return 0;
}
if (root.start == start && root.end == end) {
return root.count;
}
int mid = root.start + (root.end - root.start) / 2;
int leftCount = 0, rightCount = 0;
if (start <= mid) {
if (end <= mid) {
leftCount = query(root.left, Math.max(start, root.start), end);
} else {
leftCount = query(root.left, Math.max(start, root.start), mid);
}
}
if (end >= mid) {
if (start >= mid + 1) {
rightCount = query(root.right, start, Math.min(end, root.end));
} else {
rightCount = query(root.right, mid + 1, Math.min(end, root.end));
}
}
return leftCount + rightCount;
}```

#### Segment Tree Modify

For a `Maximum Segment Tree`, which each node has an extra value `max` to store the maximum value in this node’s interval.

Implement a `modify` function with three parameter `root`, `index` and `value` to change the node’s value with [start, end] = [index, index] to the new given value. Make sure after this change, every node in segment tree still has the max attribute with the correct value.

Example

For segment tree:

```<code>                      [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]
</code>```

if call `modify(root, 2, 4)`, we can get:

```<code>                      [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]
</code>```

or call `modify(root, 4, 0)`, we can get:

```<code>                      [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]
</code>```
Note

We suggest you finish problem Segment Tree Build and Segment Tree Query first.

Challenge

Do it in `O(h)` time, h is the height of the segment tree.

Share