Advanced Data Structure-Line Segment Tree

Listen to the author's sayings

Today is a very heavy day, CCF officials came in to cancel OI, do not know whether it is true.
OIer s don't give up their dreams! We must march forward bravely!
This line of trees will be very difficult. At least I think so. But I dared to write this blog after all kinds of experiments!

What do I want you to do with the segment tree?

Suppose I give you an interval that allows you to do this as quickly as possible: modify one of the subintervals, query the values of another subinterval, and repeat these operations. You would say: for loop. Yes, this complexity is O(N) segment tree can be said to be an interval artifact. It has four basic functions of interval processing: single point query, single point modification, interval query, interval modification. In addition to the complexity of O(NlogN) required for tree building, the complexity of other operations is O(logN).
Let's start with a graph of a segment tree.

The numbers here are dots, not point values.
Detailed analysis of subsequent updates.
Microparsing is provided in the code.
The complete code is as follows:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxm 10001
int n,a[maxm],sum[maxm],delta[maxm];

void update(int x){sum[x]=sum[x<<1]+sum[x<<1|1];return;}
//Here we count the values of the left and right sub-nodes and pay them to ourselves. Every value update needs to be updated once.
//X<<1|1 is equivalent to x*2+1. If you have any queries, you can see the following connection.
//https://blog.csdn.net/Martisum/article/details/96182646

//This function is used to mark down
void pushdown(int now,int l,int r){
	int mid=(l+r)>>1;
	if(delta[now]!=0){
		sum[now<<1]+=delta[now]*(mid-l+1);
		//All leaf nodes contained in each right node need to be updated, so multiply by the number of leaf nodes.
		delta[now<<1]+=delta[now];
		//Of course, the right node also needs to be marked with laziness
		//Left node repeat operation
		sum[now<<1|1]+=delta[now]*(r-mid);
		delta[now<<1|1]+=delta[now];
		//Finally, the label is lowered, and the lazy label of the source node is zero.
		delta[now]=0;
	}
	return;
}

//Recursive tree building
void build(int now,int l,int r){
	if(l==r){sum[now]=a[l];return;}
	int mid=(l+r)>>1;
	//Recursive processing left and right
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	//Finish the processing (to the smallest) and then gradually count it up.
	update(now);
	return;
}

//This is a single point modification.
void changepoint(int now,int l,int r,int x,int v){
	//If l==r indicates the value target node (because the node you are looking for must be in the interval, and you are looking for it strictly according to the left-right principle, so it must be)
	if(l==r){sum[now]+=v;return;}
	int mid=(l+r)>>1;
	//Remember to put the laziness mark down
	pushdown(now,l,r);
	//On the left (left of mid), look for the left, and vice versa.
	if(x<=mid){changepoint(now<<1,l,mid,x,v);}
	else{changepoint(now<<1|1,mid+1,r,x,v);}
	//Old rules [funny by hand], your father will change if you change them, so update
	update(now);
	return;
}

//This is a single-point query.
int askpoint(int now,int l,int r,int x){
	//If l==r indicates the value target node (because the node you are looking for must be in the interval, and you are looking for it strictly according to the left-right principle, so it must be)
	if(l==r){return sum[now];}
	int mid=(l+r)>>1;
	pushdown(now,l,r);
	//It's almost the same process as a single point of modification, right?
	if(x<=mid){return askpoint(now<<1,l,mid,x);}
	else{return askpoint(now<<1|1,mid+1,r,x);}
	//You see there is no need to update the query.
}

int askrange(int now,int l,int r,int tl,int tr){
	//If the current control interval is included by the target interval, the current interval value is returned directly.
	if(tl<=l&&r<=tr) return sum[now];
	int mid=(l+r)>>1,ans=0;
	pushdown(now,l,r);
	//Otherwise, look left and right. Give the results of each level of recursion to the ans, and count them recursively at each level.
	if(tl<=mid){ans+=askrange(now<<1,l,mid,tl,tr);}
	if(tr>mid){ans+=askrange(now<<1|1,mid+1,r,tl,tr);}
	return ans;
}

void changerange(int now,int l,int r,int tl,int tr,int v){
	//If it is included, the lazy label is generated directly and interval assignment is performed.
	//V stands for adding v!!!!!!! Not for this interval.
	if(tl<=l&&r<=tr){sum[now]+=(r-l+1)*v;delta[now]+=v;return;}
	int mid=(l+r)>>1;
	pushdown(now,l,r);
	//Processing left and right
	if(tl<=mid){changerange(now<<1,l,mid,tl,tr,v);}
	if(tr>mid){changerange(now<<1|1,mid+1,r,tl,tr,v);}
	update(now);
	return;
}

int main(){
	std::ios::sync_with_stdio(false);
	freopen("tin.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];}
	build(1,1,n);
	
	freopen("CON","r",stdin);
	int k,b,c;
	char ju;
	LOOP:cout<<"What do you want to do?"<<endl;
	cout<<"1.Interval modification"<<endl<<"2.Interval query"<<endl<<"3.Single point modification"<<endl<<"4.Single point query"<<endl<<"5.Sign out"<<endl;
	cin>>ju;
	if(ju=='1'){
		cout<<"input l,r,v";
		cin>>k>>b>>c;cout<<endl;
		changerange(1,1,n,k,b,c);
	}else if(ju=='2'){
		cout<<"input l,r";
		cin>>k>>b;cout<<endl;
		cout<<"The result is:"<<askrange(1,1,n,k,b)<<endl;
	}else if(ju=='3'){
		cout<<"input p,v";
		cin>>k>>b;
		changepoint(1,1,n,k,b);
		cout<<endl;
	}else if(ju=='4'){
		cout<<"input p";
		cin>>k;
		cout<<"The result is:"<<askpoint(1,1,n,k)<<endl;
	}else if(ju=='5'){goto FINA;}
	goto LOOP;
	FINA:cout<<"Quit successfully"<<endl;
	
	return 0;
}

Tags: iOS

Posted on Mon, 07 Oct 2019 11:43:20 -0700 by CodeToad