Segment Tree with Lazy Markers for Interval Modification and Interval Finding

summary

Writing is messy, maybe only you can understand ORZ

For interval modifications, single-point lookup problems and single-point modifications, interval lookup problems are used Binary Index Tree The time complexity of O(logN) can be solved well, but for interval modification, interval lookup is not.Thus, a data structure called the number of segments is used, similar to a heap (where the node number is n, the left child number is 2n, and the right child number is 2n+1).The original array is A[1~10].The structure of the segment tree is shown below, pictured from Lougu Valley.
From the figure above, you can see that the root node represents t[1] for A[1]+A[2]+...+A[10]
The left node of the root node indicates t[2]=A[1]+...+A[mid] (mid = (1+10)/2)
The right node of the root node indicates t[3]=A[mid+1]+...+A[10]
Therefore, when looking for numbers and times within an interval (nl,nr), you can start at the root node.
The steps for interval accumulation are as follows:

If the current node contains an interval between (nl,nr), the value of the node can be returned directly.Otherwise, split it up and find his left and right children recursively.Recursive code can be easily written out.

The steps for single point modification are as follows:

If a single point modification is required, all nodes along the path can only be modified by traversing from the root node to the corresponding leaf node at that point.

Interval Modification

However, if interval modification is required, the complexity will be more than O(logN).
At this time, if you add a lazy tag to the tree (tag array, each node has a value of the lazy tag), you can solve the interval modification problem very well.The role of the lazy marker is explained below.

  • Example
  • Step 1: When we need to add 2 to A[1~10] (nl=1,nr=10), we start traversing from the root node (node number 1) and the range of the root node is included by (nl,nr). Then directly increase c[1] by 2*10 (because c[1] represents the sum of A[1-10]), and then add 2 to tag[1], indicating that the number of the range of the node needs to be increased by 2.End traversal.Below is a picture.
  • Step 2: When you need to increase A[1~6] (nl=1,nr=6) by 3, because nl,nr cannot contain the range of Node 1 [1-10], you need to traverse from Node 1 to Node 2 and 3.The operation at this time is to pass the node of tag[1] (multiplied by the number of the following node elements) to nodes 2 (1-5) and 3 (6-10), then set the tag[1] to zero.Make the first judgment described above.For Node 2, because [1-6] contains the range [1-5] of Node 2, add Node 2 directly, and make tag[2]=3. Use tag[2] to save the number of nodes that need to be added below.Jump out of recursion to Node 2.In the process of determining node 3, it is necessary to traverse all the way to the lowest six nodes in order for them to be included by (nl,nr).At the end of the recursive traversal of the two-child node, you need to go back to the two-child node and add it to the parent node, that is, t[1] = t[2]+t[3] (where tag[1] has been cleared) to go back.
  • The meaning of a tag node: tag[1]=4 means that all elements [1-10] of the range contained by the node (1) need to be added 4.

Interval lookup

After solving the problem of interval modification, the steps of interval finding only need to be modified slightly.

When the traversed node cannot be contained by (nl,nr), that is, when it needs to be split, pass the lazy flag on first, then recurse the child.

Example 1

P3372 [Template] Segment Tree 1
The AC code is as follows

#include<cstdio>

#define ll long long
const int maxn = 300005;	//Tree nodes must be at least doubled
//It also seems good to use a structure for the range and values of the storage nodes!
ll t[maxn];	//Segment tree 
ll tag[maxn];	//To speed up interval insertion, introduce a lazy flag

void f(int node,int left,int right,ll v){	
	//Each element of the node interval adds v
	tag[node]+=v;
	t[node]+=v*(right-left+1);
	return;
}

void push_down(int node,int left,int right){
	//Pass the lazy tag of the node to the child node
	int mid = (left+right)>>1;
	f(node*2  ,left ,mid  ,tag[node]);
	f(node*2+1,mid+1,right,tag[node]);
	tag[node] = 0;
	return;
}

void update(int node,int left,int right,int nl,int nr,ll v){	//Interval modification [nl~nr] plus v 
	//Node: current node; range of left,right nodes; range of nl,nr original array
	if(nl<=left&&right<=nr){
		t[node] += v*(right-left+1);
		tag[node] += v;
		return;
	}
	push_down(node,left,right);	//Pass the lazy flag of the node down
	int mid = (left+right)>>1;
	if(nl<=mid) update(node*2,left,mid,nl,nr,v);
	if(mid+1<=nr) update(node*2+1,mid+1,right,nl,nr,v);
	t[node] = t[node*2]+t[node*2+1];//To flash back 
	return;
}

ll getsum(int node,int left,int right,int nl,int nr){	//Sum of Intervals 
	if(nl<=left&&right<=nr)
		return t[node];	//The node range is covered by intervals that need to be summed
    int mid=(left+right)>>1;
    push_down(node,left,right);	//Pass on the lazy flag
    ll res=0;
    if(nl<=mid)
		res+=getsum(node*2,left,mid,nl,nr);
    if(mid+1<=nr) 
		res+=getsum(node*2+1,mid+1,right,nl,nr);
    return res;
}

int n,m;//Number of digits, number of operations 
int main(){
	scanf("%d %d",&n,&m);
	int o,x,y;
	ll k;
	for(int i=1;i<=n;i++){
		scanf("%lld",&k);
		update(1,1,n,i,i,k);//nums[i] plus k 
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&o);
		if(o==1){
			scanf("%d %d %lld",&x,&y,&k);//Plus k in [x~y] 
			update(1,1,n,x,y,k);
		}else{
			scanf("%d %d",&x,&y);
			printf("%lld\n",getsum(1,1,n,x,y));
		}
	}
	return 0;
}

Example 2

P3373 [Template] Segment Tree 2

Looking at the title, we found that only two lazy markers were needed to represent multiplication and addition.Then you need to specify a priority by:

(1) Addition takes precedence, that is, segtree[root2].value=((segtree[root2].value+segtree[root].add)segtree[root].mul)%p. The problem is that it is very difficult to update if you change the value of add, mul will also interactively turn into a strange fraction and lose precision, which we refuse internally;
(2) Multiplication priority, that is, specify segtree[root2]. value= (segtree[root2]. value segtree[root]. mul+segtree[root]. add* (the length of this interval)%p, so if changing the value of add only changes add, multiply add by the corresponding value when changing mul, without loss of precision, it looks good.- zhuwanman

So choose Multiplication first.You can modify it slightly by following the example of Segment Tree Example 1.
AC code.

#include<cstdio>

#define ll long long
const int maxn = 300005;	//Tree nodes must be at least doubled
//It also seems good to use a structure for the range and values of the storage nodes!
ll t[maxn];	//Segment tree 
ll tag_mul[maxn]; //Lazy Sign 
ll tag_add[maxn]; //Lazy Mark
int p;
//Addition takes precedence, that is, segtree[root*2].value=((segtree[root*2].value+segtree[root].add)*segtree[root].mul)%p,
//The problem is that it is very difficult to update in this case. If you change the value of add, mul will also be linked into a strange fractional loss of precision, which we are very internal rejection;
//Multiplication priority, that is, segtree[root*2].value=(segtree[root*2].value*segtree[root].mul+segtree[root].add* (length of this interval)%p,
//In this case, if changing the value of add only changes add, multiply add by the corresponding mul when changing mul. Without loss of precision, it looks good.
//https://www.luogu.com.cn/problemnew/solution/P3373 Multiply by analysis selection
 
void f(int node,int left,int right,ll v_mul,ll v_add){	//Accept multiplication and laziness marks 
	//Each element of the node interval is multiplied by a lazy flag before a lazy flag 
	tag_add[node] = (tag_add[node] * v_mul+v_add)%p;
	tag_mul[node] = (tag_mul[node] * v_mul)%p;
	t[node] = (v_mul*t[node] +v_add*(right-left+1))%p;
	return;
}

void push_down(int node,int left,int right){
	//Pass the lazy tag of the node to the child node
	int mid = (left+right)>>1;
	f(node*2  ,left ,mid  ,tag_mul[node],tag_add[node]);
	f(node*2+1,mid+1,right,tag_mul[node],tag_add[node]);
	tag_add[node] = 0;
	tag_mul[node] = 1;
	return;
}

void update_add(int node,int left,int right,int nl,int nr,ll v){	//Interval modification [nl~nr] plus v 
	//Node: current node; range of left,right nodes; range of nl,nr original array
	if(nl<=left&&right<=nr){
		t[node] =(t[node] + v*(right-left+1))%p;
		tag_add[node] += v;
		return;
	}
	push_down(node,left,right);	//Pass the lazy flag of the node down
	int mid = (left+right)>>1;
	if(nl<=mid) update_add(node*2,left,mid,nl,nr,v);
	if(mid+1<=nr) update_add(node*2+1,mid+1,right,nl,nr,v);
	t[node] = (t[node*2]+t[node*2+1])%p;//To flash back 
	return;
}

void update_mul(int node,int left,int right,int nl,int nr,ll v){	//Interval modifications [nl~nr] are multiplied by v 
	//Node: current node; range of left,right nodes; range of nl,nr original array
	if(nl<=left&&right<=nr){
		t[node] =(t[node]*v)%p;
		tag_add[node] *= v;
		tag_mul[node] *= v;
		return;
	}
	push_down(node,left,right);	//Pass the lazy flag of the node down
	int mid = (left+right)>>1;
	if(nl<=mid) update_mul(node*2,left,mid,nl,nr,v);
	if(mid+1<=nr) update_mul(node*2+1,mid+1,right,nl,nr,v);
	t[node] = (t[node*2]+t[node*2+1])%p;//To flash back  
	return;
}


ll getsum(int node,int left,int right,int nl,int nr){	//Sum of Intervals 
	if(nl<=left&&right<=nr)
		return t[node];	//The node range is covered by intervals that need to be summed
    int mid=(left+right)>>1;
    push_down(node,left,right);	//Pass on the lazy flag
    ll res=0;
    if(nl<=mid)
		res+=getsum(node*2,left,mid,nl,nr);
    if(mid+1<=nr) 
		res+=getsum(node*2+1,mid+1,right,nl,nr);
    return res%p;
}

int n,m;//Number of digits, number of operations 
int main(){
	for(int i=1;i<=maxn;i++)
		tag_mul[i] = 1;
	scanf("%d %d %d",&n,&m,&p);
	int o,x,y;
	ll k;
	for(int i=1;i<=n;i++){
		scanf("%lld",&k);
		update_add(1,1,n,i,i,k);//nums[i] plus k 
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&o);
		if(o==1){
			scanf("%d %d %lld",&x,&y,&k);//Plus k in [x~y] 
			update_mul(1,1,n,x,y,k);
		}else if(o==2){
			scanf("%d %d %lld",&x,&y,&k);//Plus k in [x~y] 
			update_add(1,1,n,x,y,k);
		}else{
			scanf("%d %d",&x,&y);
			printf("%lld\n",getsum(1,1,n,x,y));
		}
	}
	return 0;
}
Twenty-two original articles were published, 8 were praised, and 2231 were visited
Private letter follow

Posted on Tue, 10 Mar 2020 18:10:33 -0700 by yarnold