线段树（Segment Tree）详解

// SegmentTree 定义线段树结构
type SegmentTree struct {
    tree  []int64    // 存储线段树节点的数组
    lazy  []int64    // 懒惰标记数组
    data  []int64    // 原始数据数组
    n     int        // 原始数组长度
    merge func(int64, int64) int64  // 节点合并函数，可以是求和、最大值、最小值等
}

// NewSegmentTree 初始化线段树
// arr: 原始数组
// mergeFunc: 节点合并函数，定义如何合并两个子节点的信息
func NewSegmentTree(arr []int64, mergeFunc func(int64, int64) int64) *SegmentTree {
    n := len(arr)
    tree := make([]int64, 4*n) // 开4倍空间确保足够
    lazy := make([]int64, 4*n)
    data := make([]int64, n)
    copy(data, arr)

    st := &SegmentTree{
        tree:  tree,
        lazy:  lazy,
        data:  data,
        n:     n,
        merge: mergeFunc,
    }
    
    // 构建线段树
    st.buildTree(0, 0, n-1)
    return st
}

// buildTree 构建线段树
// node: 当前节点在tree数组中的索引
// start, end: 当前节点表示的区间范围
func (st *SegmentTree) buildTree(node, start, end int) int64 {
    // 叶子节点
    if start == end {
        st.tree[node] = st.data[start]
        return st.tree[node]
    }

    // 递归构建左右子树
    mid := start + (end-start)/2
    leftNode := 2*node + 1
    rightNode := 2*node + 2

    leftSum := st.buildTree(leftNode, start, mid)
    rightSum := st.buildTree(rightNode, mid+1, end)

    // 合并子节点信息
    st.tree[node] = st.merge(leftSum, rightSum)
    return st.tree[node]
}

// pushDown 下推懒惰标记
func (st *SegmentTree) pushDown(node, start, end int) {
    // 如果没有懒惰标记，直接返回
    if st.lazy[node] == 0 {
        return
    }

    // 计算左右子节点
    leftNode := 2*node + 1
    rightNode := 2*node + 2
    mid := start + (end-start)/2

    // 更新左子节点
    st.tree[leftNode] += st.lazy[node] * int64(mid-start+1)
    st.lazy[leftNode] += st.lazy[node]

    // 更新右子节点
    st.tree[rightNode] += st.lazy[node] * int64(end-mid)
    st.lazy[rightNode] += st.lazy[node]

    // 清除当前节点的懒惰标记
    st.lazy[node] = 0
}

// QueryRange 查询区间[l,r]的信息
func (st *SegmentTree) QueryRange(l, r int) int64 {
    if l < 0 || r >= st.n || l > r {
        panic("Invalid range")
    }
    return st.queryRange(0, 0, st.n-1, l, r)
}

// queryRange 内部查询函数
func (st *SegmentTree) queryRange(node, start, end, l, r int) int64 {
    // 如果当前区间完全在查询区间外
    if start > r || end < l {
        return 0 // 根据具体问题返回合适的默认值
    }

    // 如果当前区间完全在查询区间内
    if l <= start && end <= r {
        return st.tree[node]
    }

    // 处理懒惰标记
    st.pushDown(node, start, end)

    // 分别查询左右子区间
    mid := start + (end-start)/2
    leftNode := 2*node + 1
    rightNode := 2*node + 2

    leftSum := st.queryRange(leftNode, start, mid, l, r)
    rightSum := st.queryRange(rightNode, mid+1, end, l, r)

    return st.merge(leftSum, rightSum)
}

// UpdateRange 更新区间[l,r]中的值，增加val
func (st *SegmentTree) UpdateRange(l, r int, val int64) {
    if l < 0 || r >= st.n || l > r {
        panic("Invalid range")
    }
    st.updateRange(0, 0, st.n-1, l, r, val)
}

// updateRange 内部更新函数
func (st *SegmentTree) updateRange(node, start, end, l, r int, val int64) {
    // 如果当前区间完全在更新区间外
    if start > r || end < l {
        return
    }

    // 如果当前区间完全在更新区间内
    if l <= start && end <= r {
        // 更新当前节点
        st.tree[node] += val * int64(end-start+1)
        // 如果不是叶子节点，添加懒惰标记
        if start != end {
            st.lazy[node] += val
        }
        return
    }

    // 处理懒惰标记
    st.pushDown(node, start, end)

    // 分别更新左右子区间
    mid := start + (end-start)/2
    leftNode := 2*node + 1
    rightNode := 2*node + 2

    st.updateRange(leftNode, start, mid, l, r, val)
    st.updateRange(rightNode, mid+1, end, l, r, val)

    // 更新当前节点
    st.tree[node] = st.merge(st.tree[leftNode], st.tree[rightNode])
}

// 使用示例
func Example() {
    // 创建一个支持区间求和的线段树
    arr := []int64{1, 3, 5, 7, 9, 11}
    st := NewSegmentTree(arr, func(a, b int64) int64 {
        return a + b
    })

    // 查询区间和
    sum := st.QueryRange(1, 3) // 查询区间[1,3]的和：3+5+7=15

    // 更新区间
    st.UpdateRange(1, 4, 2) // 将区间[1,4]中的每个数都加2

    // 再次查询
    newSum := st.QueryRange(1, 3) // 现在是(3+2)+(5+2)+(7+2)=21
}

// 查询区间最大值的线段树
func NewMaxSegmentTree(arr []int64) *SegmentTree {
    return NewSegmentTree(arr, func(a, b int64) int64 {
        if a > b {
            return a
        }
        return b
    })
}

// 查询区间最小值的线段树
func NewMinSegmentTree(arr []int64) *SegmentTree {
    return NewSegmentTree(arr, func(a, b int64) int64 {
        if a < b {
            return a
        }
        return b
    })
}

// 查询区间GCD的线段树
func NewGCDSegmentTree(arr []int64) *SegmentTree {
    return NewSegmentTree(arr, func(a, b int64) int64 {
        return gcd(a, b)
    })
}

// 辅助函数：计算最大公约数
func gcd(a, b int64) int64 {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}