Notes d'apprentissage ACM: arbre de segment

Linno 2021-08-19 23:52:15 阅读数:334

notes apprentissage acm arbre 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

Copyright:Cet article est[Linno]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2021/08/20210819235136214Z.html