Stupid line segment tree , An analysis of the fool number

Line segment tree

Definition :

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 .
Using line segment tree can quickly find the number of times a node appears in several line segments , The time complexity is O(logN). And not optimized Spatial complexity by 2N, In practical application, it usually needs to be opened 4N To avoid crossing the bounds , So sometimes discretization is needed to compress space .
What's the usage? ?
Line tree is powerful , Support Sum of intervals , Interval maximum , Interval modification , Single point modification Wait for the operation .
The idea of line tree is very similar to the idea of divide and conquer .
Each node of the line tree stores an interval [L…R] Information about , Among them, the 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 modification 、 The time complexity of the query is only O(log 2n).
Build up trees :
void build(int l,int r,int i){// Build up trees , Is the current left boundary ,r For the right border ,i Is number 
tree[i].l=l;// Update boundary values
tree[i].r=r;
if(l==r){// If it's the bottom node ,sum Is itself
tree[i].sum=input[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,2*i);// The left part of the building
build(mid+1,r,2*i+1);// The right part of the building
tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum)%mod;// Update on recursive return sum value
}

  Interval modification :

void add(int i,int L,int R,int k){// Interval modification   ;
if(tree[i].l>=L&&tree[i].r<=R){// Be fully contained
tree[i].sum=tree[i].sum+(tree[i].r-tree[i].l+1)*k; // Modification interval
tree[i].lazy+=k;// Update delay flag
return ;
}
push_down(i);// If you don't include it completely, pass down the lazy mark first
int mid=(tree[i].l+tree[i].r)/2;
if(L<=mid) add(2*i,L,R,k);// There's overlap on the left. Go left
if(mid<R) add(2*i+1,L,R,k);// There's overlap on the right. Go right
// It must not be written here mid<=R, Otherwise, there will be a dead cycle
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum// to update sum value
}

Interval query :

int ask(int i,int L,int R){// Interval query 
if(tree[i].l>=L&&tree[i].r<=R) return tree[i].sum;// It's all about , The reason is the same as interval modification
push_down(i);// Send down delay flag without full inclusion
int ans=0;
int mid=(tree[i].l+tree[i].r)/2;
if(mid>=L) ans=(ans+ask(2*i,L,R));
if(mid<R) ans=(ans+ask(2*i+1,L,R));// Record answer
return ans;
}

Downlink delay flag (push_down operation ):

void push_down(int i){// Delay mark down 
if(tree[i].lazy){
tree[2*i].sum=(tree[2*i].sum+(tree[2*i].r-tree[2*i].l+1)* tree[i].lazy%mod)%mod;
tree[2*i+1].sum=(tree[2*i+1].sum+(tree[2*i+1].r-tree[2*i+1].l+1)* tree[i].lazy%mod)%mod;
tree[2*i].lazy+=tree[i].lazy;
tree[2*i+1].lazy+=tree[i].lazy;
tree[i].lazy=0;
}
}

The function of delay marking :

Sometimes you don't have to query if you modify it , So we put a delay mark on it , Pass it down when you need it .

Board questions :https://www.luogu.com.cn/problem/P3372

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int type,x,y,k;
long long input[N];
struct node {
int l;
int r;
long long sum;
long long add;
} tree[N*4]; void spread(int i) {
if(tree[i].add) {
tree[2*i].sum+=tree[i].add*(tree[2*i].r-tree[2*i].l+1);
tree[2*i+1].sum+=tree[i].add*(tree[2*i+1].r-tree[2*i+1].l+1);
tree[2*i].add+=tree[i].add;
tree[2*i+1].add+=tree[i].add;
tree[i].add=0;
}
} void build(int i,int l,int r) {
tree[i].l=l;
tree[i].r=r;
if(l==r) {
tree[i].sum=input[l];
return ;
}
int mid=(l+r)/2;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
} void change(int i,int l,int r,int k) {
if(l<=tree[i].l&&r>=tree[i].r) {
tree[i].sum+=k*(tree[i].r-tree[i].l+1);
tree[i].add+=k;
return ;
}
spread(i);
int mid=(tree[i].l+tree[i].r)/2;
if(l<=mid)change(2*i,l,r,k);
if(r>mid)change(2*i+1,l,r,k);
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
} long long check(int i,int l,int r) {
if(l<=tree[i].l&&r>=tree[i].r) {
return tree[i].sum;
}
spread(i);
long long flag=0;
int mid=(tree[i].l+tree[i].r)/2;
if(l<=mid) flag+=check(2*i,l,r);
if(r>mid) flag+=check(2*i+1,l,r);
return flag;
} int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>input[i];
}
build(1,1,n);
for(int i=1; i<=m; i++) {
cin>>type;
if(type==1) {
cin>>x>>y>>k;
change(1,x,y,k);
}
if(type==2) {
cin>>x>>y;
cout<<check(1,x,y)<<endl;
}
}
return 0;
}

OK, next comes ——

Tree analysis

Definition : We divide a tree into several vertical chains according to some rules , Each maintenance can jump one chain at a time 、 And with the help of some powerful linear data structure to maintain ( Usually the number of chains is small ), This greatly optimizes the time complexity , Enough to solve many problems of linear structure moving to trees .

  Variable :

//son[N]  Heavy son's number , If there is no heavy son, the number is -1
//size[N] Size of subtree
//f[N] The number of the parent node
//d[N] The depth of the node
//top[N] At the end of the chain
//id[N] New number after heavy chain dissection
//rk[N] Yes rk[id[i]]=i

In the process of splitting a tree into chains , We're going to do it twice dfs:

void dfs1(int x,int fa,int depth){//x: The current node  fa: The parent node  depth: Current node depth 
f[x]=fa;// Update parent
d[x]=depth;// Update depth
size[x]=1;// Subtree size initialization : The root node itself
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==fa) continue ;
dfs1(y,x,depth+1);
if(size[y]>size[son[x]]) son[x]=y;// Update heavy son
size[x]+=size[y];// Update subtree size
}
return ;
} //dfs1 to update f[N],d[N],size[N],son[N]
 void dfs2(int u,int t){//u Is the current node ,t For chain segments 
top[u]=t;
id[u]=++cnt;
rk[cnt]=u;// New number
if(!son[u]) return ;
dfs2(son[u],t);// Give priority to your son , Make serial numbers on a chain
for(int i=head[u];i;i=nex[i]){
int y=ver[i];
if(y==son[u]||y==f[u]) continue;
dfs2(y,y);// Build another chain
}
}//dfs2 to update top[N],id[N],rk[N]

So far, the process of our dissection has been completed , Now let's see what's the use of tree chaining in the topic :

subject :https://www.luogu.com.cn/problem/P3384

We are required to do the following operations :

operation  1: Format : 1 x y z  To remove a tree from  x  To  y  The values of all nodes on the shortest path of a node are added with  z.( Interval modification )

operation  2: Format : 2 x y  It means to seek a tree from  x  To  y  The sum of the values of all nodes on the shortest path of a node .( Interval query )

operation  3: Format : 3 x z  That will be  x  Add... To the values of all nodes in the subtree of the root node  z.( Interval modification )

operation  4: Format : 4 x  Express to  x  Is the sum of the values of all nodes in the subtree of the root node .( Interval query )

Operation 1 :

void func1(int x,int y,int k){// Remove the tree from the tree  x To  y The values of all nodes on the shortest path of a node are added with k
if(d[x]<d[y]) swap(x,y);
while(top[x]!=top[y]){// loop , Until these two points are in the same chain
if(d[top[x]]<d[top[y]]) swap(x,y);// standard
add(1,id[top[x]],id[x],k);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);// The one with shallow depth must be the one with smaller serial number
add(1,id[x],id[y],k);
}

In fact, the principle is the same as Multiply the demand LCA almost .

Operation two :

void func2(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=(ans+ask(1,id[top[x]],id[x]))%mod;
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);// Same as above
ans=(ans+ask(1,id[x],id[y]));
cout<<ans%mod<<endl;
}

The principle and func1 Almost. ~

Operation three && Operation 4 :

The treatment here is more ingenious .

In the tree section , The number of a chain is continuous , Therefore, the number of a subtree is also continuous .

So just use the interval modification and interval query operation of line segment tree .

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,root,mod;
int idx=0;
struct node{
int l;
int r;
int sum;
int lazy;
}tree[4*N];
int head[N],ver[2*N],nex[2*N],son[N],size[N],f[N],d[N],top[N],id[N],rk[N];
int input[N];
int cnt=0;
void add_e(int x,int y){
ver[++idx]=y;
nex[idx]=head[x];
head[x]=idx;
} void build(int l,int r,int i){// Conventional achievements
tree[i].l=l;
tree[i].r=r;
if(l==r){
tree[i].sum=input[rk[l]]%mod;
return ;
}
int mid=(l+r)/2;
build(l,mid,2*i);
build(mid+1,r,2*i+1);
tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum)%mod;
} void push_down(int i){// Delay mark down
if(tree[i].lazy){
tree[2*i].sum=(tree[2*i].sum+(tree[2*i].r-tree[2*i].l+1)* tree[i].lazy%mod)%mod;
tree[2*i+1].sum=(tree[2*i+1].sum+(tree[2*i+1].r-tree[2*i+1].l+1)* tree[i].lazy%mod)%mod;
tree[2*i].lazy+=tree[i].lazy;
tree[2*i+1].lazy+=tree[i].lazy;
tree[i].lazy=0;
}
} int ask(int i,int L,int R){// Interval query
if(tree[i].l>=L&&tree[i].r<=R) return tree[i].sum;
push_down(i);
int ans=0;
int mid=(tree[i].l+tree[i].r)/2;
if(mid>=L) ans=(ans+ask(2*i,L,R))%mod;
if(mid<R) ans=(ans+ask(2*i+1,L,R))%mod;
return ans%mod;
} void add(int i,int L,int R,int k){// Interval modification ;
if(tree[i].l>=L&&tree[i].r<=R){
tree[i].sum=(tree[i].sum+(tree[i].r-tree[i].l+1)*k%mod)%mod;
tree[i].lazy+=k;
return ;
}
push_down(i);
int mid=(tree[i].l+tree[i].r)/2;
if(L<=mid) add(2*i,L,R,k);
if(mid<R) add(2*i+1,L,R,k);
tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum)%mod;
} void dfs1(int x,int fa,int depth){//x: The current node fa: The parent node depth: Current node depth
f[x]=fa;// Update parent
d[x]=depth;// Update depth
size[x]=1;// Subtree size initialization : The root node itself
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==fa) continue ;
dfs1(y,x,depth+1);
if(size[y]>size[son[x]]) son[x]=y;// Update heavy son
size[x]+=size[y];// Update subtree size
}
return ;
} void dfs2(int u,int t){//u Is the current node ,t For chain segments
top[u]=t;
id[u]=++cnt;
rk[cnt]=u;// New number
if(!son[u]) return ;
dfs2(son[u],t);// Give priority to your son , Make serial numbers on a chain
for(int i=head[u];i;i=nex[i]){
int y=ver[i];
if(y==son[u]||y==f[u]) continue;
dfs2(y,y);// Build another chain
}
} void func1(int x,int y,int k){// Remove the tree from the tree x To y The values of all nodes on the shortest path of a node are added with k
if(d[x]<d[y]) swap(x,y);
while(top[x]!=top[y]){// loop , Until these two points are in the same chain
if(d[top[x]]<d[top[y]]) swap(x,y);// standard
add(1,id[top[x]],id[x],k);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);// The one with shallow depth must be the one with smaller serial number
add(1,id[x],id[y],k);
} void func2(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=(ans+ask(1,id[top[x]],id[x]))%mod;
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);// Same as above
ans=(ans+ask(1,id[x],id[y]));
cout<<ans%mod<<endl;
}
signed main(){
cin>>n>>m>>root>>mod;
for(int i=1;i<=n;i++){
cin>>input[i];// Enter the initial value of the node
}
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
add_e(x,y);
add_e(y,x);// Drawing
}
dfs1(root,0,1);// for the first time dfs seek son,depth,f,size
dfs2(root,root);// The second time dfs seek id,rk, Split the tree into a linked list
build(1,n,1);// Build up trees
for(int i=1;i<=m;i++){
int type;
cin>>type;
if(type==1){
int x,y,z;
cin>>x>>y>>z;
func1(x,y,z);
}
if(type==2){
int x,y;
cin>>x>>y;
func2(x,y);
}
if(type==3){
int x,z;
cin>>x>>z;
add(1,id[x],id[x]+size[x]-1,z);
}
if(type==4){
int x;
cin>>x;
cout<<ask(1,id[x],id[x]+size[x]-1)%mod<<endl;
}
}
return 0;
}

End of the flower **,°*:.*( ̄▽ ̄)/$:*.°** .

 

Line segment tree & More related articles on number chain partition

  1. G - Game HDU - 5242 ( Number chain division )

    Topic link : G - Game HDU - 5242 The main idea of the topic : First of all T Group test sample , Give a star to 1 Trees with nodes as roots , Each node has its own value , Yes m The second chance to go down from the root node to the leaf node , Every time, we get the weights of all the passing nodes ...

  2. Number chain division ( Statistics of trees Count )

    Topic link :https://cn.vjudge.net/contest/279350#problem/C Specific ideas : Single point update , Interval query , There are two operations when querying , Query interval maximum and interval sum . Be careful : At the time of inquiry ...

  3. Number chain division (Aragorn&#39;s Story )

    Topic link :https://vjudge.net/contest/279350#problem/A The main idea of the topic :n A little bit ,m side , then q Time to ask , Because in the tree , Two points define a straight line , We can do this for all the values on this line ...

  4. POJ 2352 Stars Line segment tree Count the stars

    Reprinted from  http://www.cnblogs.com/fenshen371/archive/2013/07/25/3214927.html The question : It is known that n The coordinates of two stars . Every star has a level , The number is equal to the coordinates ...

  5. Number chain division (Tree)

    Topic link :https://cn.vjudge.net/contest/279350#problem/D The main idea of the topic : operation , Single point query , Interval negation , Ask the maximum of the interval . AC Code : #include<ios ...

  6. Number chain division (Housewife Wind )

      Topic link :https://vjudge.net/contest/279350#problem/B The main idea of the topic : Here you are. n,q,s.n It means to have n A little bit ,q On behalf of q Time to ask ,s It represents the starting point . And then there will be n-1 strip ...

  7. UOJ#30/Codeforces 487E Tourists Point biconnected component ,Tarjan, Round square tree , The tree chain splits , Line segment tree

    Link to the original text https://www.cnblogs.com/zhouzhendong/p/UOJ30.html Subject portal - UOJ#30 The question uoj It's very concise . Clear , I won't copy it here . Answer key First build ...

  8. POJ 2763 Housewife Wind 【 The tree chain splits 】+【 Line segment tree 】

    < Topic link > The main idea of the topic : Given an undirected tree , This tree has border power , The number of the edges of this tree is completely determined by the number of the input edges . Give you a starting point , Do two operations : One : The person goes from the starting point to the designated point , What's the total weight of this path . ...

  9. BZOJ1758[Wc2010] Reconstruction plan —— Fractional programming + A long chain splits + Line segment tree + Two points answer + Tree form DP

    Title Description Input The first line contains a positive integer N, Express X The number of cities in China . The second line contains two positive integers L and U, It refers to the upper and lower limits of the number of roads to be built in the first phase of the reconstruction plan required by the policy Next N-1 Describe the original plan of the reconstruction team , Three positive integers per line Ai, ...

  10. On tree chain partition (C++、 Algorithm 、 Tree structure )

    On the number chain partition I see on the Internet, there are several better explanations , This article is mainly about AC Comments to code ( Thank you witer The supply of ) This is the explanation http://www.cnblogs.com/kuangbin/archive/2013 ...

Random recommendation

  1. Use local JConsole Monitoring remote JVM ( turn )

    The problem background   Tomcat Frequent breakdown crash, Want to see JVM Memory usage , I think of using Jconsole monitor , It used to be just monitoring local JVM, This time we need to monitor the remote , There are many problems .   After hours of hard work , There are many references ...

  2. 【C++11】30 Minutes to understand C++11 New characteristics

    author : Wang Xuanyi , Source :http://www.cnblogs.com/neverdie/ Welcome to reprint , Please also retain this statement . If you like this article , Please order [ recommend ]. thank you ! What is? C++11 C++11 It was once called C+ ...

  3. PHP SOAP

    <?php $classmap = array(); // Notice the difference from example one $soap = new SoapServer(null, array('uri' => "http: ...

  4. PageRank A mistake in a simple implementation

    In one of my blogs PageRank in , stay 5.1 There was a mistake in the simple part of the algorithm implementation . This mistake also reflects my understanding of PageRank The algorithm has a bias in understanding . What kind of mistake is this ? That's true : In a simple implementation, each ...

  5. rsync Unauthorized access exploit

    Vulnerability description :rsync yes Linux Data image backup tool under the system , Use the fast incremental backup tool Remote Sync Remote synchronization is possible , Support local replication , Or with others ssh,rsync Host synchronization . That is, if you can connect to the target IP Of r ...

  6. Raspberry pie Pin and interface diagram AV Interface sequence

    Raspberry pie Pin figure notes : This form is applicable to all versions of , And compatible 26Pin Raspberry pie B, Raspberry pie B by 26Pin, Its pins correspond to the front of the above table 26Pin.   Raspberry pie Interface diagram AV The interface is also called (RCA),AV Interface is a kind of interface that appeared earlier ...

  7. CSDN Personalization of blog columns

    Han Meng Feisha   Han Yafei  313134555@qq.com  yue31313  han_meng_fei_sha ====== <a href=" http://weibo.com/23 ...

  8. C Language &#183; Calculate age

    Calculate age British mathematician De Morgan was born in 19 century ( namely 18xx year ). He was very talented when he was young . Once someone asked his age , And he said : “ here we are x The square of , I happen to be x year ”. Please calculate , In what year was de Morgan born . The year in the question ...

  9. LDA Summary

    1.Blei Of LDA Code (C):http://www.cs.princeton.edu/~blei/lda-c/index.html2.D.Bei The home page of :http://www.cs.princeton ...

  10. Java Thread interview questions Top 50( turn ImportNew)

    Whether you're a new programmer or an old hand , You must have encountered some thread problems in the interview .Java An important feature of the language is its built-in support for concurrency , Give Way Java It is very popular with enterprises and programmers . Most of the well paid Java Development positions require developers to be proficient in multithreading ...