Explanation of line segment tree

What is a segment tree ？

Line segment tree , It's a kind of Binary search tree . It divides an interval into several Unit interval , Each node stores an interval . it Powerful , Support interval summation , Interval maximum , Interval modification , Single point modification and other operations .
Each node of the line tree stores an interval [L…R] Information about , among Leaf node L=R .
Its general idea is ： Divide a large interval equally into 2 Between communities , Each cell is divided equally into 2 It's a small area …… And so on , Up to the... Of every interval L be equal to R（ In this way, the interval only contains the information of one node , Can't be divided ）. By modifying these intervals 、 Inquire about , To achieve the modification of the large interval 、 Inquire about .
thus , Every single point of modification 、 The time complexity of a single point query is only O (logn) .

The basic structure and construction of line segment tree

The length of each segment tree is not 1 The interval of is divided into left and right intervals to solve recursively , The whole line segment is divided into a tree structure , The information of the interval is obtained by merging the information of the left and right intervals . This data structure can easily perform most interval operations .

There is a size of 5 Array of a={10,11,12,13,14}, To convert it to a segment tree , There are the following ways ： Let the root node number of the segment tree be 1, Using arrays d To save our segment tree ,di It is used to save the segment tree numbered i The value of the node （ The value maintained by each node here is the sum of the intervals represented by this node ）.

1. Why drive 4 Times the interval ？

2. Delay marking ： Add a new tag in the node structure , Record whether this node will be modified , Modification of any interval , We first divide it into nodes in the segment tree by interval query , Then modify the information of these nodes , And mark these nodes . When modifying and querying , If we get to a node P, And continue to view its child nodes , So we have to look at the nodes P Whether it's marked , If there is , You need to modify the information of the child node first according to its tag , And the child nodes are marked with the same marks , Also cancel the node P The tag , This operation is called tag dropping , Also called pushDown

It's understandable , Suppose grandpa wants to give new year's money to his two granddaughters , So Grandpa gave his son the total lucky money first , Let the son give it to the daughter
, But the son thinks his daughter is too young , Temporarily unavailable , So I saved it first . Suddenly one day, Grandpa was going to ask his granddaughter if she got the lucky money , At this time, dad was worried , I quickly gave my daughter the lucky money