当前位置:网站首页>Segment tree and number chain partition

Segment tree and number chain partition

2021-02-23 17:58:54 Top zero

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(log2n).
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 **,°*:.*( ̄▽ ̄)/$:*.°** .

 

 

 

 

 

 

版权声明
本文为[Top zero]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/02/20210223175804102z.html

随机推荐