# 线段树

（有关线段树的定义来自LintCode网站的相关题目

## 描述

• 根节点的 startend`build` 方法所给出。
• 对于节点 A 的左儿子，有 `start=A.left, end=(A.left + A.right) / 2`
• 对于节点 A 的右儿子，有 `start=(A.left + A.right) / 2 + 1, end=A.right`
• 如果 start 等于 end, 那么该节点是叶子节点，不再有左右儿子。

## 说明

• 查找给定的点包含在了哪些区间内
• 查找给定的区间包含了哪些点

```               [1,  6]
/        \
[1,  3]           [4,  6]
/     \           /     \
[1, 2]  [3,3]     [4, 5]   [6,6]
/    \           /     \
[1,1]   [2,2]     [4,4]   [5,5]```

# 线段树的构造

```class SegmentTreeNode:
def __init__(self, start, end):
self.start, self.end = start, end
self.left, self.right = None, None```

```class Solution:
# @param start, end: Denote an segment / interval
# @return: The root of Segment Tree
def build(self, start, end):
if start > end: return None
root = SegmentTreeNode(start, end)
root.left = None if start == end else self.build(start, (start + end) // 2)
root.right = None if start == end else self.build((start + end) // 2 + 1, end)
return root
```

# 线段树的修改

## 最大线段树

node.max = max(node.left.max, node.right.max)

```class SegmentTreeNode:
def __init__(self, start, end):
self.start, self.end, self.max = start, end, 0
self.left, self.right = None, None
class Solution:
def build(self, start, end):
if start > end: return None
root = SegmentTreeNode(start, end)
root.left = None if start == end else self.build(start, (start + end) // 2)
root.right = None if start == end else self.build((start + end) // 2 + 1, end)
root.max = 0
return root```

## 线段树的修改

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

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

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

1. 如果root节点为空直接返回
2. 判断index是否在root区间内
3. 是的话根据情况修改root区间的max值为value，再对root的左右节点分别进行modify操作，否的话直接返回

```class Solution:
def modify(self, root, index, value):
if root and root.start <= index <= root.end:
root.max = max(root.max, value)
self.modify(root.left, index, value)
self.modify(root.right, index, value)```

# 线段树的查询

```class Solution:
def query(self, root, start, end):
mid = (root.start + root.end) // 2
if start == root.start and end == root.end:
return root.max
elif end <= mid:
return self.query(root.left, start, end)
elif start >= mid + 1:
return self.query(root.right, start, end)
else:
return max(self.query(root.left, start, mid),
self.query(root.right, mid + 1, end))```

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

```class SegmentTreeNode:
def __init__(self, start, end):
self.start, self.end, self.max = start, end, 0
self.left, self.right = None, None
class Solution:
def build(self, start, end):
if start > end: return None
root = SegmentTreeNode(start, end)
root.left = None if start == end else self.build(start, (start + end) // 2)
root.right = None if start == end else self.build((start + end) // 2 + 1, end)
root.max = 0
return root
def modify(self, root, index, value):
if root and root.start <= index <= root.end:
root.max = max(root.max, value)
self.modify(root.left, index, value)
self.modify(root.right, index, value)
def query(self, root, start, end):
mid = (root.start + root.end) // 2
if start == root.start and end == root.end:
return root.max
elif end <= mid:
return self.query(root.left, start, end)
elif start >= mid + 1:
return self.query(root.right, start, end)
else:
return max(self.query(root.left, start, mid),
self.query(root.right, mid + 1, end))```

# 线段树的其他应用

```class SegmentTreeNode:
def __init__(self, start, end):
self.start, self.end, self.total = start, end, 0
self.left, self.right = None, None
class Solution:
def build(self, start, end):
if start > end: return None
root = SegmentTreeNode(start, end)
root.left = None if start == end else self.build(start, (start + end) // 2)
root.right = None if start == end else self.build((start + end) // 2 + 1, end)
root.total = 0
return root
def modify(self, root, index, value):
if root and root.start <= index <= root.end:
root.total += value
self.modify(root.left, index, value)
self.modify(root.right, index, value)
def query(self, root, start, end):
mid = (root.start + root.end) // 2
if start == root.start and end == root.end:
return root.total
elif end <= mid:
return self.query(root.left, start, end)
elif start >= mid + 1:
return self.query(root.right, start, end)
else:
return self.query(root.left, start, mid) + self.query(root.right, mid + 1, end)```

# 结语

28 篇文章32 人订阅

0 条评论

## 相关文章

### java 集合框架(List操作)

/*list 基本操作 * * List a=new List(); * 增 * a.add(index,element);按指定位置添加，其余元素...

1271

### Golang语言”奇怪用法“有哪些？

1，go的变量声明顺序是：”先写变量名，再写类型名“，此与C/C++的语法孰优孰劣，可见下文解释： http://blog.golang.org/gos-dec...

32710

### 1082 线段树练习 3 区间查询与区间修改

1082 线段树练习 3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description ...

2705

### PHP数据结构（二十五） ——并归排序

PHP数据结构（二十五）——并归排序 （原创内容，转载请注明来源，谢谢） 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

4028

2957

### 面试必备：30 个 Java 集合面试问题及答案

Java集合框架为Java编程语言的基础，也是Java面试中很重要的一个知识点。这里，我列出了一些关于Java集合的重要问题和答案。

1462

1012

3235

### PHP数据结构（二十一） ——希尔排序

PHP数据结构（二十一）——希尔排序 （原创内容，转载请注明来源，谢谢） 一、概述 希尔排序，又称缩小增量排序，也属于插入排序类方法，时间上有较大改进。前面...

3527

942