线段树

基础与数据结构

说明

每个节点表示一个区间的聚合值；区间查询与单点更新为 O(log n)。

分析

叶节点存放原数组，内部节点保存左右子区间之和。查询半开区间 [l,r) 时，从两侧向上移动并累加被完整覆盖的节点。

示例补齐4片叶子为[2,3,5,0]，查询[0,2)直接取左子树和5。查询将目标分为不重叠的完整区间；换成求最小值时单位元应为正无穷，不能照搬补零。

查看图表代码

适用前提与边界

构建需要 O(n) 时间与空间；示例展示区间和，单点更新可沿叶到根路径同步修改。 查询范围按原数组长度限定为0≤l≤r≤len(a)；内部补齐槽不能当成真实元素，Sum(l,l)返回0。

示例输入与调用

tree := NewSegmentTree([]int{2, 3, 5})
	fmt.Println(tree.Sum(0, 2))

运行输出

5

完整 Go 示例

package main

import "fmt"

type SegmentTree struct {
	n    int
	tree []int
}

func NewSegmentTree(a []int) *SegmentTree {
	n := 1
	for n < len(a) {
		n *= 2
	}
	t := &SegmentTree{n, make([]int, 2*n)}
	copy(t.tree[n:], a)
	for i := n - 1; i > 0; i-- {
		t.tree[i] = t.tree[2*i] + t.tree[2*i+1]
	}
	return t
}
func (t *SegmentTree) Sum(l, r int) int {
	l += t.n
	r += t.n
	s := 0
	for l < r {
		if l%2 == 1 {
			s += t.tree[l]
			l++
		}
		if r%2 == 1 {
			r--
			s += t.tree[r]
		}
		l /= 2
		r /= 2
	}
	return s
}

func main() {
	tree := NewSegmentTree([]int{2, 3, 5})
	fmt.Println(tree.Sum(0, 2))
}