Detailed explanation of line segment tree (including tested code implementation)

Catalog

1. Introduction to segment tree

2. Principle and implementation of line segment tree

2.1 Interval modification

 2.2 Interval query

 2.3 Interval update

---

1. Introduction to segment tree

What is a segment tree ？ Line tree is a kind of Binary search tree , And Interval tree be similar , It divides an interval into some cell intervals , Each cell interval corresponds to a leaf node in the line segment tree . [1] 

For each non Leaf node [a,b], Its left son represents the interval [a,(a+b)/2], The range represented by the right son is [(a+b)/2+1,b]. So the segment tree is Balanced binary trees , The last number of child nodes is N, That is, the length of the whole segment interval .

Using line segment tree can quickly find the number of times a node appears in several line segments , Time complexity by O(logN）. And not optimized Spatial complexity by 2N, So sometimes discretization is needed to compress space .----- From Baidu .

2. Principle and implementation of line segment tree

The segment tree is mainly a large interval Divide evenly Maintain between two sections , Then use the values between cells to update the large interval . In this way, the correctness can be guaranteed , It can also keep time at log ⁡ Level （ Because this segment tree is balanced ）. That is to say a [L,R] The interval will be divided into two intervals [L,(L+R)/2] and [(L+R)/2+1,R] Between these two communities . Then recursion goes down to divide directly L=R.
Below is a tree [ 1 , 10 ] Decomposition process of line segment tree （ Nodes of the same color are on the same layer ） As shown in the figure ：

  We can find out , The maximum depth of this segment tree does not exceed [ log2   ( n − 1 ) ]+2.

1. The basic framework of implementation  

How do we implement this structure ？ Is it really a binary tree ？ Of course not. We can use the heap we learned before to realize this structure . In this paper, we use full binary tree to realize segment tree , Maybe Lao tie will ask if the length of the given array is not 2 To the power of ？ Here, if he is not a full binary tree, we will make him a full binary tree . 

2. Calculation of space

I use large root heap to realize line generation tree , This is because the big root heap is a complete binary tree, so we can use arrays to represent , Only when the length of the array is not 2^i We need to make up . As shown in the figure

  Now let's estimate how much space we need . Suppose the interval has n Elements , For a full binary tree ：

1. First floor to k There are 2^k-1 Nodes （ There are about 2^k） Nodes

2. The last floor has 2^k-1 Nodes

We can figure out ： The number of nodes in the last layer of the full binary tree is about the sum of the number of previous nodes

 1. If n=2^i You need to 2n Nodes

2. If n=2^i+1 At this time, the worst situation requires 4*n Nodes （ Estimated value ）

3. Representation ：

  Here, the subscript of our array is from 1 Start , This is to enable the subscripts of left and right children to use bit operations to improve efficiency . If the index of a parent node is i Then there is the following formula ：

1. Left the child =2*i;

2. The right child =2*i+1

Expressed as ：

1. Left the child =i<<1;

2. The right child =i<<1|1;

 4. The construction of segment tree corresponds to the code ：

#pragma once 
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
class SegmentTree {
public:
	SegmentTree(const vector<int>& origin) {
		MAXN = origin.size() + 1;
		arr.resize(MAXN);
		for (int i = 1; i < MAXN; i++) {//arr[0] Don't go from arr[1] Start 
			arr[i] = origin[i - 1];
		}
		sum.resize(MAXN << 2);// Equivalent to MAXN*4; To support the concept of brain tonic , The accumulation and information of a certain range 
		lazy.resize(MAXN << 2);// To support the concept of brain tonic , One does not accumulate and mark down 
		change.resize(MAXN << 2);
		update.resize(MAXN << 2);

	}
	void build(int l, int r, int rt) {
		if (l == r) {// There's only one number 
			sum[rt] = arr[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, rt << 1);
		build(mid + 1, r, (rt << 1) | 1);// amount to 2*rt+1;                                                                                                                                                                                                 
		pushUp(rt);// The calculation game returns the cumulative sum upward 
	};
	void pushUp(int rt) {
		sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1];//rt<<1|1 amount to 2*rt+1;
	}
private:
	int MAXN;
	vector<int>arr;//arr Maintain the original sequence information from 0 Start , But here arr from 1 Start 
	vector<int>sum;// Simulated line segment tree maintains intervals and 
	vector<int>lazy;// Mark for accumulated lazy information 
	vector<int>change;// The updated value of the corresponding position 
	vector<bool>update;// To update the lazy tag 
};

2.1 Interval modification

The modification can be roughly divided into two steps ：

1. Find this section .

2. Modify all points in this interval

The general flow is as follows ：

1. If the current interval is completely covered in the target interval, this interval sum Add （r-l+1)*C

2. If it is not completely covered, the lazy flag will be sent down first

3. If the left child of this interval intersects with the target interval , Then recursively assign tasks to the left child

4. If the right child of this interval intersects with the target interval , Then recursively assign tasks to the right child .

Lazy update ： 

In order to improve efficiency, laziness and novelty are introduced into the line segment tree ：

1. The meaning of the mark ： The interval has been updated , But the subinterval has not been updated , What is the updated information （ Interval summation only records whether it has been visited , The problem of multiple operations such as the four operations of an interval needs to record which kind of operation ）.
Here are two more important things ： Relative mark and absolute mark

Relative markers ： It refers to markers that can coexist , And the order of marking has nothing to do with the answer , That is, marks can be superimposed . For example, give all the numbers in a range + a , We can superimpose the marks , For example, I hit one last time Add 2  The tag , This time, give this section +5 , Then put + 2  The mark of becomes + 5

Absolute mark ：

Marks that cannot coexist , Every time you have to pass the mark down , Then put a new mark on the current node . These marks cannot change the order , Otherwise it will go wrong . For example, assign a new value to a number in an interval , Or carry out multiple operations for a section .

for example ：

  With A sign of laziness This magical thing , When we modify the interval, we can be lazy , First modify the current node , Then hang the information directly on the node ！
Such as the line segment tree below , When we want to modify the interval [ 1 , 4 ] [1,4][1,4] , Assign an element to 1 when , We can first find all nodes whose entire interval needs to be modified , It's obviously a storage area [1,3] and [4,4] These two nodes of . We can put [1,3] Of sum Change it to (3−1+1)∗1=3 , hold [ 4 , 4 ]   Of sum Change it to   (1-1+1)*1=1 , Then give them a value of 1   A sign of laziness , And then it's all right .
thus , Every time we modify the interval, we just need to find the target interval , There is no need to recurse down to the leaf node , So it improves efficiency .

Mark down
meet Relative markers This kind of easily bullied children , We only need to put a lazy mark on it .
however , encounter Absolute mark , Or as mentioned below Interval query , Simply marking it as lazy is obvious GG 了 . After all , A sign of laziness Simply hang a message on the node , It's impossible to encounter complicated situations ！
therefore , Laziness marks Download operation It was born .
seeing the name of a thing one thinks of its function , Mark down It is to pass the lazy mark of a node to its left and right sons , Then delete the lazy flag of this node .
Let's first review the meaning of the tag ：

The meaning of the mark ： This section has been updated , But the subinterval has not been updated , What is the updated information .

obviously , The parent interval contains child intervals , That is, the mark of the parent interval is related to the child interval . in the majority of cases , The parent and child intervals are marked same . therefore , We can deduce what mark the sub interval should be from the mark of the parent interval .
Be careful ： The following problems refer to interval assignment , Unless there is any special statement .
If you want to reassign all elements in a node to x  , Then its son must also be assigned x  . therefore , We modify it directly at the child node  sumsum value , Just change the flag of the child node （ Because the interval assignment needs Absolute mark , So when the child node has been marked , First, send down the tag of the child node , Then send down the tag of the node . But interval assignment will overwrite the value of child nodes , So in this problem , Just modify the tag directly ）

Next, add C Code for ：

void pushUp(int rt) {// Update father's cumulative sum 
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}
	void pushDown(int rt, int ln, int rn) {
		if (update[rt]) {//update The method needs to use 
			update[rt << 1] = true;// Send it down 
			update[rt << 1|1] = true;
			change[rt << 1] = change[rt];
			change[rt << 1 | 1] = change[rt];
			lazy[rt << 1] = 0;// Empty the lazy array of left and right children 
			lazy[rt << 1 | 1] = 0;
			sum[rt << 1] = change[rt] * ln;// The left child always 
			sum[rt << 1 | 1] = change[rt] * rn;// The sum of the right children 
			update[rt] = false;// The current location has been changed to false;
		}
		if (lazy[rt]) {
			lazy[rt << 1] += lazy[rt];
			lazy[(rt << 1) | 1] += lazy[rt];
			sum[rt << 1] += lazy[rt] * ln;
			sum[rt << 1 | 1] += lazy[rt] * rn;
			lazy[rt] = 0;
		}
	}
	void add(int L, int R, int C, int l, int r, int rt) {//L and R Indicates the actual scope to be modified  l To r Represents the actual range  rt  Indicates this range 
		// I'll go to that position in the array to find the information of 
		if (L <= l && r <= R) {// Laziness 
			// Modify relevant information 
			sum[rt] += C * (r - l + 1);
			lazy[rt] += C;
			return;
		}
		// The current task cannot be avoided , Unable to update , I want to send it down 
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);// First send the lazy information to the left and right children 
		if (L <= mid) {// The left child needs to assign tasks 
			add(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {// The right child needs to issue a task 
			add(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);// Update father's cumulative sum 
	}

about add Parameter interpretation in ：

1.L,R Represents the range to be modified

2.l,r Represents the actual scope

3.C Value to add

4.rt Express l To r Get the information about the position in the array

about pushdown Interpretation of method ：

1. It includes update Methods and add Lazy operation  

 2.2 Interval query

Sum of interval queries add similar ：

1. If the current interval is completely covered in the target interval, it will be for sum The data of the location is returned

2. If it is not completely covered, the lazy flag will be sent down first

3. If the left child of this interval intersects with the target interval , Then recursively assign tasks to the left child

4. If the right child of this interval intersects with the target interval , Then recursively assign tasks to the right child .

The corresponding code ：

long long query(int L, int R, int l, int r, int rt) {
		if (L <= l && r <= R) {// Just cover this interval and get the value directly in it 
			return sum[rt];
		}
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);// First assign lazy information to left and right children 
		long long ans = 0;
		if (L <= mid) {
			ans+=query(L, R, l, mid, rt << 1);
		}
		if (R > mid) {
			ans += query(L, R, mid + 1, r, rt << 1 | 1);
		}
		return ans;
	}

 2.3 Interval update

Interval update and interval modification are basically similar, but also different

1. If a certain interval is set to the corresponding number, then the lazy Set all the data in the array to 0

2. If you can't be lazy in the current range, you should first send lazy information to the left and right children to assign tasks

Please refer to the code for details. ：

void Update(int L, int R, int C, int l, int r, int rt) {
		if (L <= l && r <= R) {
			update[rt] = true;// The tag has been updated 
			change[rt] = C;
			sum[rt] = C * (r - l + 1);
			lazy[rt] = 0;// Empty 
			return;
		 }
		// The current task cannot be avoided , Unable to update , I want to send it down 
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);
		if (L <= mid) {
			Update(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {
			Update(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);// Update the cumulative sum of the parent node 
	}

Corresponding total code ：

#pragma once 
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
class SegmentTree {
public:
	SegmentTree(const vector<int>& origin) {
		MAXN = origin.size() + 1;
		arr.resize(MAXN);
		for (int i = 1; i < MAXN; i++) {//arr[0] Don't go from arr[1] Start 
			arr[i] = origin[i - 1];
		}
		sum.resize(MAXN << 2);// Equivalent to MAXN*4; To support the concept of brain tonic , The accumulation and information of a certain range 
		lazy.resize(MAXN << 2);// To support the concept of brain tonic , One does not accumulate and mark down 
		change.resize(MAXN << 2);
		update.resize(MAXN << 2);

	}
	void build(int l, int r, int rt) {
		if (l == r) {
			sum[rt] = arr[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, rt << 1);
		build(mid + 1, r, rt << 1 | 1);// amount to 2*rt+1;                                                                                                                                                                                                 
		pushUp(rt);
	};
	void pushUp(int rt) {// Update father's cumulative sum 
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}
	void pushDown(int rt, int ln, int rn) {
		if (update[rt]) {//update The method needs to use 
			update[rt << 1] = true;// Send it down 
			update[rt << 1|1] = true;
			change[rt << 1] = change[rt];
			change[rt << 1 | 1] = change[rt];
			lazy[rt << 1] = 0;// Empty the lazy array of left and right children 
			lazy[rt << 1 | 1] = 0;
			sum[rt << 1] = change[rt] * ln;// The left child always 
			sum[rt << 1 | 1] = change[rt] * rn;// The sum of the right children 
			update[rt] = false;// The current location has been changed to false;
		}
		if (lazy[rt]) {// Send lazy messages 
			lazy[rt << 1] += lazy[rt];
			lazy[(rt << 1) | 1] += lazy[rt];
			sum[rt << 1] += lazy[rt] * ln;
			sum[rt << 1 | 1] += lazy[rt] * rn;
			lazy[rt] = 0;
		}
	}
	void add(int L, int R, int C, int l, int r, int rt) {//L and R Indicates the actual scope to be modified  l To r Represents the actual range  rt  Indicates this range 
		// I'll go to that position in the array to find the information of 
		if (L <= l && r <= R) {// Laziness 
			// Modify relevant information 
			sum[rt] += C * (r - l + 1);
			lazy[rt] += C;
			return;
		}
		// The current task cannot be avoided , Unable to update , I want to send it down 
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);// First send the lazy information to the left and right children 
		if (L <= mid) {// The left child needs to assign tasks 
			add(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {// The right child needs to issue a task 
			add(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);// Update father's cumulative sum 
	}
	void Update(int L, int R, int C, int l, int r, int rt) {
		if (L <= l && r <= R) {
			update[rt] = true;// The tag has been updated 
			change[rt] = C;
			sum[rt] = C * (r - l + 1);
			lazy[rt] = 0;// Empty 
			return;
		 }
		// The current task cannot be avoided , Unable to update , I want to send it down 
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);
		if (L <= mid) {
			Update(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {
			Update(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);// Update the cumulative sum of the parent node 
	}

	
	long long query(int L, int R, int l, int r, int rt) {
		if (L <= l && r <= R) {// Just cover this interval and get the value directly in it 
			return sum[rt];
		}
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);// First assign lazy information to left and right children 
		long long ans = 0;
		if (L <= mid) {
			ans+=query(L, R, l, mid, rt << 1);
		}
		if (R > mid) {
			ans += query(L, R, mid + 1, r, rt << 1 | 1);
		}
		return ans;
	}
private:
	int MAXN;
	vector<int>arr;//arr Maintain the original sequence information from 0 Start , But here arr from 1 Start 
	vector<int>sum;// Simulated line segment tree maintains intervals and 
	vector<int>lazy;// Mark for accumulated lazy information 
	vector<int>change;// The updated value of the corresponding position 
	vector<bool>update;// To update the lazy tag 
};

The above code bloggers have been tested to be basically correct. If there are errors, please leave a message in the comment area ！