Introduction and template of segment tree Foundation (I)

Basic introduction and template of line segment tree ( One )

Recently learned the practical structure of line segment tree , I also learned many articles written by big men on my blog , So I want to try to write a blog by myself , Deepen the understanding . I am ACM The last one is waste Adorable new , I hope the big guys can give me more advice , Thank you very much .

First part The concept of line segment tree

The segment tree can be used to store a set of arrays ,
The structure of the segment tree itself is a binary tree , Each node stores two kinds of data , The first is the starting point and ending point of the interval , The second is the interval sum of this interval .

The following picture is quoted from the article of the boss Line segment tree From entry to advanced （ Super clear , Simple and easy to understand ） Although I learned from this big guy .

As shown in the figure, this is the length of 4 The line segment tree formed by the array of , Array 1~4 There is no stored value in （ Subscript from 1 Start ） The blue numbers represent the left and right endpoints of the interval , Leaf nodes represent array subscripts .

At this point, if the array 1~4 Assign the values to 1,2,3,4. This line segment tree grows like this , Red numbers represent numerical values , The leaf node just corresponds to the... Of the array 1,2,3,4.

I know what a segment tree is , So how do we build a segment tree , The second part answers this question .

Second parts Create a line tree

The method I use is to use the structure array to save the tree , As well as the return of achievements . First, post the code I created

#include<stdio.h>
#define N 50003
int date[N];
struct nod
{
    
	int l,r;// Represents the left and right endpoints  
	int sum;// Interval and  
}Tree[4*N];// Note the size of the array  

void build(int l,int r,int i)// Build up trees   initial l=0,r=n-1,i=0. Each corresponds to the first of the original array , The last subscript and the subscript of the root node of the segment tree 
{
    
	Tree[i].l=l, Tree[i].r=r;
	
// If the left and right endpoints are equal, we recurse to the leaf node , After assigning the original array to the node, you can return  
	if(l==r)
	{
    
		Tree[i].sum = date[l];
		return ;
	}
	int mid = (l+r)>>1;// Find the midpoint , and mid=(l+r)/2 identical 
	// Recursive tree building  
	build(l, mid, i*2+1); // Be careful i How the values change 
	build(mid+1,r,i*2+2);
	
	// Remember to add the values of the child node to the parent node when returning  
	Tree[i].sum = Tree[i*2+1].sum + Tree[i*2+2].sum;
	return ;
}

It should be noted that , When building a tree, you should open the space to the... Of the original array 4 times .
And the variation formula of node subscript , I choose 0 As the subscript of the root node , So the left child subscript is the parent node i2+1, The right son is i2+2. If you choose to 1 As root node , The formula becomes i2 and i2+1, Try drawing a binary tree .

Third parts Single point modification

The basic purpose of segment tree is to modify and query multiple times , Perhaps simple interval sum queries using prefixes and can achieve better results O(1) Level , But if you add q For the second modification of a single point or interval, we have to select the segment tree Only segment trees qwq. Next, we introduce the basic maintenance of the segment tree —— Single point modification .
If yes 3 Make changes （+2 The operation of ） First recursively find the leaf node 3, add 2, And then all the way back to all along the way 2.

Post my code

void change(int index,int k,int i)//index Is the subscript i want to change ,k Is the value that needs to be changed  
{
    
	if(Tree[i].l == Tree[i].r)// Find the leaf node , take sum add k 
	{
     
		Tree[i].sum+=k;
		return ;
	}
	int mid = (Tree[i].l+Tree[i].r)>>1;
	if(mid >= index) change(index,k,i*2+1);// If mid>=index We go into the left subtree to find  
	else if(mid < index) change(index,k,i*2+2);// Enter the right subtree to find  
	
	Tree[i].sum = Tree[i*2+1].sum + Tree[i*2+2].sum;// Don't forget that the parent node also needs to add this k 
	return ;	
}

Um. , Don't forget to mid>=index, I forgot to add... The first time I wrote it =, And then gorgeous Idiot Of wa 了 .

Fourth parts Interval query

Finally, we introduce interval query , The time complexity can reach O(logn) The level of , It is also very excellent .

int search(int l,int r,int i)//l,r Subscript the left and right endpoints of the interval to be queried  
{
    
	int ans=0;
	if(Tree[i].l>=l&&Tree[i].r<=r)// If the query interval is completely included , Go straight back to sum that will do  
	{
    
		return Tree[i].sum;
	}
	
	if(Tree[i].l>r||Tree[i].r<l)// If not included at all, return 0 
	{
    
		return 0;
	}
	
	if(Tree[i*2+1].r>=l) ans+=search(l,r,i*2+1);// The left child has an intersection with the goal , Just check the left subtree  
	if(Tree[i*2+2].l<=r) ans+=search(l,r,i*2+2);// Empathy  
	return ans;
}

Be careful , Because the data is not big, I only use int, But most topics need to use long long At the beginning of the tree building sum So it is with .

Links to template questions ： The enemy troops were arrayed （ Single point modification , Interval query ）
And the complete code of the template question

#include<stdio.h>
#define N 50003
int date[N];
struct nod
{
    
	int l,r;// Represents the left and right endpoints  
	int sum;// Interval and  
}Tree[4*N];// Note the size of the array  

void build(int l,int r,int i)// Build up trees  
{
    
	Tree[i].l=l, Tree[i].r=r;
	if(l==r)// If the left and right endpoints indicate that we recurse to the leaf node , After assigning the original array to the node, you can return  
	{
    
		Tree[i].sum = date[l];
		return ;
	}
	int mid = (l+r)>>1;// Find the midpoint , and mid=(l+r)/2 identical 
	// Recursive tree building  
	build(l, mid, i*2+1); 
	build(mid+1,r,i*2+2);
	
	// Remember to add the values of the child node to the parent node when returning  
	Tree[i].sum = Tree[i*2+1].sum + Tree[i*2+2].sum;
	return ;
}

void change(int index,int k,int i)//index Is the subscript i want to change ,k Is the value that needs to be changed  
{
    
	if(Tree[i].l == Tree[i].r)// Find the leaf node , take sum add k 
	{
     
		Tree[i].sum+=k;
		return ;
	}
	int mid = (Tree[i].l+Tree[i].r)>>1;
	if(mid >= index) change(index,k,i*2+1);// If mid>=index We go into the left subtree to find  
	else if(mid < index) change(index,k,i*2+2);// Enter the right subtree to find  
	
	Tree[i].sum = Tree[i*2+1].sum + Tree[i*2+2].sum;// Don't forget that the parent node also needs to add this k 
	return ;	
}
 
int search(int l,int r,int i)//l,r Subscript the left and right endpoints of the interval to be queried  
{
    
	int ans=0;
	if(Tree[i].l>=l&&Tree[i].r<=r)// If the query interval is completely included , Go straight back to sum that will do  
	{
    
		return Tree[i].sum;
	}
	
	if(Tree[i].l>r||Tree[i].r<l)// If not included at all, return 0 
	{
    
		return 0;
	}
	
	if(Tree[i*2+1].r>=l) ans+=search(l,r,i*2+1);// The left child has an intersection with the goal , Just check the left subtree  
	if(Tree[i*2+2].l<=r) ans+=search(l,r,i*2+2);// Empathy  
	return ans;
}
 
int main()
{
    
	int T,i,j,k,n,sum;
	char a[10];
	scanf("%d",&T);
	for(k=1;k<=T;k++)
	{
    
		scanf("%d",&n);
		for(i=0;i<n;i++)
		scanf("%d",&date[i]);
		
		build(0,n-1,0);
		
		printf("Case %d:\n",k);
		while(scanf("%s",a)&&a[0]!='E')
		{
    
			scanf("%d %d",&i,&j);
			if(a[0]=='A'||a[0]=='S') {
    
				if(a[0]=='S') j=0-j;
				change(i-1,j,0);
			}
			
			if(a[0]=='Q'){
    
				sum=search(i-1,j-1,0);
				printf("%d\n",sum);
			}
		}
	}
	return 0;
}

Some advanced things may be updated in the future , If you can't wait to learn more , You can go to the big guy blog linked above to learn .