线段树（Segment Tree）
一句话说明
线段树就是把区间不断二分，每个节点只负责一段区间的答案。
Go 代码：区间和
type SegmentTree struct {
n int
tree []int
}
func NewSegmentTree(nums []int) *SegmentTree {
st := &SegmentTree{n: len(nums), tree: make([]int, 4*len(nums))}
if len(nums) > 0 {
st.build(1, 0, len(nums)-1, nums)
}
return st
}
func (st *SegmentTree) build(node, left, right int, nums []int) {
if left == right {
st.tree[node] = nums[left]
return
}
mid := left + (right-left)/2
st.build(node*2, left, mid, nums)
st.build(node*2+1, mid+1, right, nums)
st.tree[node] = st.tree[node*2] + st.tree[node*2+1]
}
func (st *SegmentTree) Query(l, r int) int {
var query func(node, left, right int) int
query = func(node, left, right int) int {
if l <= left && right <= r {
return st.tree[node]
}
mid := left + (right-left)/2
ans := 0
if l <= mid {
ans += query(node*2, left, mid)
}
if r > mid {
ans += query(node*2+1, mid+1, right)
}
return ans
}
return query(1, 0, st.n-1)
}关键点
节点维护什么信息，决定了线段树能解决什么问题。区间和、最大值、最小值、懒标记，都是同一套骨架。