Notes d'apprentissage ACM: arbre de segment

title : Arbre de segment
date : 2021-8-15
tags : ACM,Structure des données

 

Arbre de segment

Segment Tree Foundation

Tout d'abord, passez en revue l'écriture de base de l'arbre de segment.

//Plaque de fondation P3372 【Modèle】Arbre de segment 1
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,k,q; 
long long arr[100005],tree[270000],lazy[270000];
​
void build(int node,int l,int r){  //Construire un arbre 
 if(l==r){
  tree[node]=arr[l];
  return;
 }
 int mid=(l+r)/2;
 build(node*2,l,mid); //Construire un arbre dans la section gauche 
 build(node*2+1,mid+1,r); //Construire un arbre dans la section droite 
 tree[node]=tree[node*2]+tree[node*2+1]; //Section et 
}
​
void pushdown(int node,int start,int end){ //Opération descendante 
 int mid=(start+end)/2;
 if(lazy[node]){ 
  tree[node*2]+=lazy[node]*(mid-start+1); // Mettre à jour les intervalles et 
  tree[node*2+1]+=lazy[node]*(end-mid);
  lazy[node*2]+=lazy[node]; // Signe paresseux vers le bas 
  lazy[node*2+1]+=lazy[node];
 }
 lazy[node]=0;
}
​
void update(int node,int start,int end,int l,int r,int c){ //Opération de mise à jour 
 if(l<=start&&end<=r){ //Si l'intervalle est dans la plage de mise à jour,Le marquage direct renvoie 
  tree[node]+=(end-start+1)*c; // Section et plus LenDoublec 
  lazy[node]+=c; // Marquage 
  return;
 }
 int mid=(start+end)/2;
 pushdown(node,start,end); // Passe en bas. 
 if(l<=mid){update(node*2,start,mid,l,r,c);} // Mettre à jour la section gauche 
 if(r>mid){update(node*2+1,mid+1,end,l,r,c);}// Mettre à jour la section droite 
 tree[node]=tree[node*2]+tree[node*2+1];  //pushup
}
​
long long query(int node,int start,int end,int l,int r){ //Opérations de requête 
 int mid=(start+end)/2;
 if(l<=start&&end<=r) return tree[node]; //Si dans le champ d'application de la requête,Retour direct 
 pushdown(node,start,end);
 long long sum=0;
 if(l<=mid) sum=query(node*2,start,mid,l,r); // Requête à gauche 
 if(r>mid) sum+=query(node*2+1,mid+1,end,l,r); // Intervalle de droite de la requête 
 return sum;
}
​
int main(){
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
 build(1,1,n);  
 while(m--){
  scanf("%d%d%d",&q,&l,&r);
  if(q==1){
   scanf("%d",&k);
   update(1,1,n,l,r,k); // Modification des intervalles 
  }else printf("%lld\n",query(1,1,n,l,r)); // Requête d'intervalle 
 }
return 0;
}

Marque de retard

Marque de retard ,Aussi appelélazy tag,Est d'ajouter un marqueur dans la section,La prochaine fois que vous accédez à cette section,Descendez à gauche et à droite（pushdown） Marquage des noeuds ,Pour compléter la modification de l'intervalle+ Enquête par intervalles .

 

Coloration des intervalles

Exemples：POJ 2528 Mayor's posters

Discrétisation des intervalles

Pour les intervalles [1,5],[2,7],[7,100],[3,1e7],Nous ne pouvons certainement pas aller directement à la section[1,1e7]Modifier,Il faut d'abord trier et discrétiser,1->1,2->2,3->3,5->4,7->5,100->6,1e7->7,Après cela, l'intervalle peut être exprimé comme[1,4],[2,5],[5,6],[3,7].Cependant, cette représentation élargit en fait la portée de l'accès,Donc, nous allons avoir plus de1Plus de chiffres entre les deux éléments,La représentation correcte est la suivante:

$$
x[1]=1,x[2]=2,x[3]=3,x[4]=4,x[5]=5,x[6]=6,x[7]=7,x[8]=100,x[9]=101,x[10]=1e7
$$

 

Nouveau noeud trouvéx[4],x[6]Et[x8], À quoi ça sert? ？

Comme si je devais peindre[1,3]->Couleur1,[5,7]->Couleur2, Avant d'ajouter [1,3]->Couleur1,[4,5]Couleur2,Les deux dernières couleurs[1,5] C'est couvert. ,En fait, il y a un autre(3,4) Couleur non traitée ;L'effet de l'ajout d'un noeud est de l'effacer[1,3],[5,7],La réponse est corrigée en comptant le nombre de couleurs.

//Mayor's posters
#include<iostream>
#include<vector>
#include<algorithm>
#define MID int mid=(p->l + p->r)>>1
using namespace std;
struct Post{ // Affiches
    int l,r;
} pst[10100];
int nodenum,cnt,ans;
int t,n,hs[10000010];
vector<int>vt;
​
struct Node{
    int l,r;
    bool full; // Section[l,r]Si elle est complètement couverte
    Node *ls, *rs; 
}tr[1000000];
​
void buildTree(Node *p, int l, int r){ //Construire un arbre 
    p->l=l;
    p->r=r;
    p->full=0; //Initialiser le noeud 
    if(l==r)return; // Si c'est une feuille ,Retour direct 
    nodenum++;
    p->ls=tr+nodenum; //Construire des sous - arbres de gauche et de droite 
    nodenum++;
    p->rs=tr+nodenum;
    MID;
    buildTree(p->ls,l,mid); //Construire un arbre dans la section gauche 
    buildTree(p->rs,mid+1,r); //Construire un arbre dans la section droite 
}
bool check(Node *p,int l,int r){ //Déterminer si l'intervalle est couvert 
    if (p->full) return false; //Déjà couvert,Cette affiche ne sera pas visible 
    if (p->l==l&&p->r==r){
        p->full=1; // Outrepasser cette section 
        return true;
   }
    bool res;
    MID;
    if(r<=mid) res=check(p->ls,l,r); // Tout à gauche. , Cherche le Sous - arbre gauche. 
    else if(l>mid) res=check(p->rs,l,r);
    else{
        bool b1=check(p->ls,l,mid);
        bool b2=check(p->rs,mid+1,r);
        res=b1||b2; //Un de ces points n'est pas couvert 
   }
    if (p->ls->full&&p->rs->full){
    p->full=1;//Si les sections gauche et droite sont couvertes,Alors cette section est couverte 
 }
    return res;
}
​
signed main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
    cin>>t;
    while(t--){
    cin>>n;
    nodenum=0,cnt=0,ans=0; //Effacer les données 
        for(int i=0;i<n;i++) {
        cin>>pst[i].l>>pst[i].r;
        vt.push_back(pst[i].l); //Placer le point d'extrémité de la section dans le conteneur 
        vt.push_back(pst[i].r);
       }
        sort(vt.begin(),vt.end());//Trier 
        vt.erase(unique(vt.begin(),vt.end()),vt.end()); //Poids mort 
        for(int i=0;i<vt.size();i++){
            hs[vt[i]]=cnt++; //Numéro de noeud du nombre d'éléments d'enregistrement 
            if(i<vt.size()-1){
                if(vt[i+1]-vt[i]>1) cnt++; //Un autre point au milieu 
           }
       } 
        buildTree(tr,0,cnt);// Démarrer la construction de l'arbre 
        for(int i=n-1;i>=0;i--){ // L'ordre inverse. ,Pour commencer sans être écrasé 
            if(check(tr,hs[pst[i].l],hs[pst[i].r])){
            ans++; //Augmentation du nombre d'affiches visibles 
   }
       }
        cout<<ans<<endl;
   }
    return 0;
}

 

Section parKGrand

En raison de la question de l'espace, ouvrez un autre billet de blog de l'arbre du Président.

 

Arbre de segment scanline

L'algorithme scanline peut être utilisé pour résoudre les problèmes de circonférence et de surface autour de plusieurs rectangles.

Algorithme scanline

Scanner l'image de bas en haut avec un fil,Calculer les réponses en scannant les bords.C'est l'équivalent de stratifier les astuces,On calcule ensuite la surface de chaque couche,Enfin, résumez les réponses.

Zone matricielle et

Compte tenu de plusieurs rectangles,Les bords doivent être parallèlesxOuyAxe.Trouvez la somme des zones de tous les rectangles.

$$
(1)Ajouter des lignes de scan aux côtés supérieur et inférieur de chaque rectangle et marquer, Le bord inférieur est marqué comme 1, Le bord supérieur est marqué comme -1\\ (2)Trier les scanlines de bas en haut,Et les côtés gauche et droit du rectangle sont triés de petit à grand\\ (3)Tenir compte de la plage de données,Nous avons procédé à la discrétisation\\ (3) Créer un arbre de segment ,L'intervalle peut alors être exprimé comme une régiony1,y2, Et longueur .\\ (4)Traverser tous les côtés adjacents à gauche et à droite,Chaque fois que la hauteur est demandée à travers l'arbre de segment,Puis la surface est additionnée.\\
$$

 

Notez que nous maintenons ici la longueur du segment, pas la valeur du point,Nous allons donc modifier l'arborescence des segments,C'est - à - dire la valeur de droite de l'enfant de gauche=La valeur gauche de l'enfant droit,..De cette façon, il n'y a pas de lacunes dans l'entretien.

// luoguP5490 【Modèle】 Scanline 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
​
struct L{
 ll x,y1,y2,flag;
 L(ll X=0,ll Y1=0,ll Y2=0,ll T=0){
  x=X,y1=Y1,y2=Y2,flag=T;
 }
}line[N<<1];
​
struct node{
 int l,r;
 ll len;
 ll lazy;
}t[N<<2];
​
int n,cnt;
ll seg[N];
map<ll,int>val;
​
ll len(int p){
 // Accès aux régions pLa hauteur de,C'est - à - dire que deux lignes de scan sont soustraites 
 return seg[t[p].r+1]-seg[t[p].l]; 
}
​
void update(int p){
 if(t[p].lazy) t[p].len=len(p); //Si cette section est marquée 
 else if(t[p].l==t[p].r) t[p].len=0; // La longueur de la section est 0 
 else t[p].len=t[p<<1].len+t[p<<1|1].len; // Ajouter deux intervalles 
}
​
void build(int p,int l,int r){ 
 t[p].l=l; //Lors de la construction de l'arbre, il suffit d'enregistrer les intervalles à gauche et à droite 
 t[p].r=r;
 if(l==r) return;
 int mid=l+r>>1;
 build(p<<1,l,mid); // Construire un arbre à gauche 
 build(p<<1|1,mid+1,r); // Construire un arbre à droite 
}
​
void change(int p,int l,int r,int k){
 if(l<=t[p].l&&t[p].r<=r){ //Si l'intervalle est dans les côtés supérieur et inférieur 
  t[p].lazy+=k; // Marquer 
  update(p); //Mettre à jour la longueur de l'intervalle 
  return;
 }
 int mid=t[p].l+t[p].r>>1;
 if(l<=mid) change(p<<1,l,r,k); // Mise à jour vers le bas 
 if(r>mid) change(p<<1|1,l,r,k);  // Plus petit vers le Haut 
 update(p); //Enfin, mettre à jour toute la section 
}
​
bool cmp(L a,L b){
 return a.x<b.x; //Selonx Tri des coordonnées 
}
​
signed main(){
 ios::sync_with_stdio(0); // Optimisation de la lecture 
 cin.tie(0);cout.tie(0);
 cin>>n;
 for(int i=1;i<=n;i++){
  ll x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  seg[++cnt]=y1; // Ajouter une ligne de scan 
  line[cnt]=L(x1,y1,y2,1); // Ajouter une ligne verticale 
  seg[++cnt]=y2;
  line[cnt]=L(x2,y1,y2,-1);
 }
 sort(line+1,line+cnt+1,cmp); // Trier les lignes verticales 
 sort(seg+1,seg+1+cnt); //Les scanlines sont triées de bas en haut 
 int m=unique(seg+1,seg+1+cnt)-(seg+1); //Poids mort 
for(int i=1;i<=m;i++) val[seg[i]]=i; //Discrétisation 
build(1,1,m); //Construire un arbre 
ll ans=0; //Notez les réponses 
for(int i=1;i<cnt;i++){ //Pourcnt-1 Bords verticaux 
int x=val[line[i].y1],y=val[line[i].y2]-1; //En haut et en bas de la zone 
change(1,x,y,line[i].flag); //Rechercher et mettre à jour la hauteur de la zone 
ans+=t[1].len*(line[i+1].x-line[i].x); //Zone d'accumulation 
 }
printf("%lld",ans); // Produit des réponses 
return 0;
}

 

Point d'ouverture dynamique

L'arbre dynamique à points ouverts permet d'éviter la discrétisation.

Si la plage de valeurs de l'arbre des segments de poids est grande,La discrétisation est difficile,Vous pouvez utiliser la technique du point d'ouverture dynamique.

L'étape de construction de l'arbre a été omise,Au lieu de cela, ajoutez des noeuds aux opérations spécifiques.

 

Références

https://oi-wiki.org/geometry/scanning/

https://mirasire.xyz/2019/11/17/SMX/

https://wmathor.com/index.php/archives/1176/

https://www.bilibili.com/video/BV1FU4y1t79g