Location>code7788 >text

Go implements dynamic open line segment tree

Popularity：0 ℃/2025-02-25 20:03:20

1. Introduction to the segment tree

A segment tree is a data structure used to efficiently process interval query and interval update. When we need to solve the problem of frequently updating interval values, we can use the segment tree structure to solve it. The core idea of ​​a segment tree is to divide the interval into multiple sub-intervals for management. The lower the interval, the smaller the range, and the root node represents the interval that the entire segment tree can represent.

This article records the way to implement dynamic open line segment tree using Go. The line segment tree of this template is used to solve the problem of interval summing, and the line segment tree that solves the minimum and maximum interval values ​​can be fine-tuned and modified.

The time complexity of interval query and interval update isO(logN)。

2. Dynamic open line segment tree implementation

The core of dynamic opening is that it needs to narrow the scope, that is, create it when entering the child nodes. Compared with using arrays to implement the line segment tree, space overhead can be reduced.

1. Line segment tree nodes

A node needs to record the sum of its left child node, right child node, and current node.val, and the lazy value that has not been pushed to the child node yetlazy。

type SegTreeNode struct {
	lazy  int
	val   int
	left  *SegTreeNode
	right *SegTreeNode
}

2. Creation of line segment tree

The entire segment tree only needs to record one root node and the last interval represented by the segment tree.

type SegTree struct {
 //The range of the line segment tree, 0~N
 N int
 root *SegTreeNode
 }

 // Create a segment tree
 func CreateSegTree(n int) *SegTree {
 return &SegTree{
 N: n,
 root: &SegTreeNode{
 lazy: 0,
 val: 0,
 left: nil,
 right: nil,
 },
 }
 }

3. Recursively push up

After updating the child node and returning to the current node, the value of the current node needs to be updated, indicating that the value is pushed from the bottom of the tree.

// Recursively push up
 func (ST *SegTree) Pushup(node ​​*SegTreeNode) {
 = +
 }

4. Lazy push down

When it is necessary to narrow the search interval, you need to search down. At this time, you must first push down the lazy value to prevent the search from finding the wrong results and prevent the child nodes from being created yet.

// Simultaneous pushdown
 func (ST *SegTree) Pushdown(node ​​*SegTreeNode, leftnum, rightnum int) {
 //Create left and right nodes
 if == nil {
 = new(SegTreeNode)
 }
 if == nil {
 = new(SegTreeNode)
 }
 //Push down node lazy mark
 if == 0 {
 Return
 }
 += leftnum *
 += rightnum *
 //Push down
 +=
 +=
 //Set zero
 = 0
 }

First, create left and right nodes first, and return directly if there is no lazy mark that needs to be pushed down. Otherwise, the left and right nodes will be updatedvalandlazy。

5. Update operation

// Update operation, update the value of the [left, right] interval, start and end are currently in the interval
 func (ST *SegTree) Update(node ​​*SegTreeNode, start, end, left, right, val int) {
 if left <= start && end <= right {
 //Lock the interval and update
 += (end - start + 1) * val
 += val
 Return
 }
 //Reduce the interval
 mid := (start + end) / 2
 //You need to find the child node, push down the lazy mark first
 (node, mid-start+1, end-mid)
 if mid >= left {
 (, start, mid, left, right, val)
 }
 if mid+1 <= right {
 (, mid+1, end, left, right, val)
 }
 	//recursion
 (node)
 }

leftandrightIndicates the interval to be updated, andstartandendIndicates the current interval. If the current interval is within the interval that needs to be updated, then directly update the interval value and lazy value, and then return directly. At this time, there is no need to continue to update the values ​​of the following nodes. This is the key to dynamically opening the point.

If the current interval is not completely within the interval that needs to be updated, divide the interval by dividing the range and narrowing the scope for updates.

For example, what needs to be updated in an operation is[30,40]The value of the range, and the current interval is[25,50]In the current interval is not completely in the update interval, then the binary is[25,37]and[38,50], both the left and right intervals and the intervals that need to be updated existIntersection, then update down until the update intervalIncludeCurrent interval.

After the update is completed, push it up.

6. Query operation

Similar to the update operation, only one is requiredansto record the answer and return.

// Query operation, return the value of the interval
 func (ST *SegTree) Query(node ​​*SegTreeNode, start, end, left, right int) int {
 if left <= start && end <= right {
 Return
 }
 mid := (start + end) / 2
 (node, mid-start+1, end-mid)
 ans := 0
 if left <= mid {
 ans += (, start, mid, left, right)
 }
 if mid+1 <= right {
 ans += (, mid+1, end, left, right)
 }
 Return ans
 }

3. Try the question

LeetCode My Schedule I

[LeetCode My Schedule III](732. My Schedule III - LeetCode)

2502. Design memory allocator - LeetCode

<Previous Next>