Segment tree is also a binary search tree. Each node of the segment tree is an interval., the leaf node is a single-point interval, that is
. For a non-leaf node, the range of its left child node is
, the interval of the right child node is
. It should be noted thatThe interval of the line segment tree is the interval of its array element subscript. The size of the interval has nothing to do with the size of the elements in the array.。
According to the above definition, the interval length of any non-root or non-leaf node in the line segment tree is half the interval length of its parent node. Therefore, the line segment tree is a balanced binary tree. The number of its leaf nodes is N, which is the length of the entire interval.
Line segment trees are widely used, mainly used for update and query operations. Generally, at least one of the updates or queries here refers to the update or query of the interval.
Figure 1 Line segment tree
An ordinary line segment tree
Node definition of line segment tree
struct Node
{ int l, r, mx; }tr[MAXN * 4]; //It is customary to open the line segment tree to 4 times the size of the original array. /* l: left endpoint of the interval r: right endpoint of the interval mx: Let l and r be the maximum value of the element in the subscript interval In fact, the line segment tree array has enough space == twice the nearest power of 2 that the original array n can reach. */
For a line segment tree array, the left child of a certain node (numbered d) is stored in 2 * d, and the right child is stored in 2 * d + 1
- In c/c++, multiplying a number by 2 to the power of 2 is: 0011 1100), expressed in decimal is to multiply or divide the operand by 2^x.
make achievements
void build(int d, int l, int r) { tr[d].l = l, tr[d].r = r; if(l == r) { tr[d].mx = arr[l]; return; } int mid = (l + r) / 2, lc = d * 2, rc = d * 2 + 1; build(lc, l, mid); build(rc, mid + 1, r); tr[d].mx = max(tr[lc].mx, tr[rc].mx); }
Generally, the operation of updating node information is called Push or PushUp. In the above tree-building example, the operation of updating node information is: tr[d].mx = max(tr[lc].mx, tr[rc].mx); This sentence is usually extracted and written into an independent function:
void Push(int d)
{ td[d].mx = max(tr[d << 1].mx, tr[d << 1 | 1].mx); }
Query
int query(int d, int l, int r)
{ //Query the maximum value within an interval if(tr[d].l == l && tr[d].r == r)return tr[d].mx; int mid = (tr[d].l + tr[d].r) / 2, lc = d * 2, rc = d * 2 + 1; if(r <= mid)return query(lc, l, mid); else if(l > mid)return query(rc, mid, r); else return max(query(lc, l, mid), query(rc, mid + 1, r)); }
The time complexity of the line segment tree query operation can reach O(logn). There is the following theorem:
Thm: When n >= 3, aThe line segment tree can be
any subinterval of
broken down into no more than
subinterval.
Updates and "Lazy Updates"
void modify(int d, int pos, int v)
{ //Change the element at position pos to v if(tr[d].l == tr[d].r && tr[d].mx == pos){ tr[d].mx = v; return; } int mid = (tr[d].l + tr[d].r) / 2, lc = d * 2, rc = d * 2 + 1; if(pos <= mid)modify(lc, pos, v); else modify(rc, pos, v); tr[d].mx = max(tr[lc].mx, tr[rc].mx); }
There is also a "lazy update" method for updating the line segment tree. The specific method is that if the updated interval completely overlaps with the interval of the current node, then only this node can be updated and this node can be marked. There is no need to update the child nodes of this node. If there is a query about this interval or its sub-interval in subsequent operations, thenIt will definitely pass through this interval, when passing through this interval again, update the mark of the starting interval, and then set the mark of this interval to "false".
Lazy update
void update(int L, int R, int val, int d){ if(Tr[d].l == L && Tr[d].r == R){ //The range is completely covered Tr[d].lazy = val; return; } int mid = Tr[d].l + Tr[d].r >> 1; if(Tr[d].lazy != 0){ //If this interval is marked, update its child nodes Tr[d << 1].lazy = Tr[d << 1 | 1].lazy = Tr[d].lazy; Tr[d].lazy = 0; } if( mid < L )update(L, R, val, d << 1 | 1); //update right subtree else if( R <= mid )update(L, R, val, d << 1); //Update left subtree else update(L, mid, val, d << 1), update(mid + 1, R, val, d << 1 | 1); }