1. Introduction to the segment tree
Line 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 structure of line segment tree 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. 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 is O(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 segment tree, space overhead can be reduced.
Line segment tree node
A node needs to record its left child node, right child node, sum of the interval represented by the current node, and lazy value lazy that has not been pushed to the child node yet.
type SegTreeNode struct {
lazy int
val int
left *SegTreeNode
right *SegTreeNode
}
Creation of 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 treefunc CreateSegTree(n int) *SegTree {
return &SegTree{
N: n,
root: &SegTreeNode{
lazy: 0,
val: 0,
left: nil,
right: nil,
},
}
}
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 upfunc (ST *SegTree) Pushup(node *SegTreeNode) {
= +
}
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 pushdownfunc (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 val and lazy of the left and right nodes will be updated.
Update operation
// Update operation, update the value of the [left, right] interval, start and end are currently in the intervalfunc (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)
}
left and right indicate the interval to be updated, while start and end indicate 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, in an operation, what needs to be updated is the value of the range [30,40], and the current interval is in [25,50], and the current interval is not completely in the update interval, so the binary is divided into [25,37] and [38,50], and both the left and right intervals have intersections with the interval that needs to be updated, so update downward until the update interval contains the current interval.
After the update is completed, push it up.
Query operation
Similar to the update operation, only ans is needed to record the answer and return it.
// Query operation, return the value of the intervalfunc (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
}This is the end of this article about the detailed explanation of the dynamic point-opening line segment tree in Go language. For more related contents of Go line segment trees, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!