Segment Tree en 2D

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
User avatar
alurquiza
Posts: 55
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Segment Tree en 2D

Postby alurquiza » Sat Nov 07, 2015 4:08 pm

Alguien me puede facilitar un codigo de Segment Tree en 2D, porque ya tengo la idea, pero no he encontrado en ninguna parte una implementacion.



User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: Segment Tree en 2D

Postby isaac » Sun Nov 08, 2015 11:22 am

No tengo idea de para que podria servir un ST en 2d. Para ejercicios similares mejor es utilizar otros medios, pero creo que te puede servir la idea de que el Segment Tree puede ser representado como una estructura autorreferenciada, donde los hijos izquierdo y derecho pueden ser construidos en tiempo de ejecucion y se ahorra una gran cantidad de memoria porque solamente se crean los nodos que realmente se necesitan. Este tipo de construccion la vi en la solucion oficial del ejercicio redoks del COCI y creo que es una buena opcion, especialmente para ejercicios como Pixels, del COJ.

User avatar
alurquiza
Posts: 55
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Re: Segment Tree en 2D

Postby alurquiza » Wed Nov 11, 2015 10:16 am

Un Segment Tree en 2D es empleado para hacer update y query sobre matrices o puntos en 2 dimensiones. El Segment tree normal funciona sobre un arreglo, es decir en 1 dimension. La idea del Segment Tree en 2D se basa en que cada nodo del Segment Tree tiene otro Segment Tree en su interor, a que la idea esta genial.

User avatar
alurquiza
Posts: 55
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Re: Segment Tree en 2D

Postby alurquiza » Thu Nov 19, 2015 2:01 pm

Les propongo este problema del SPOJ: USUBQSUB
Esta en este link:
http://www.spoj.com/problems/USUBQSUB/

Nota: El que no pueda acceder me puede escribir al correo: alurquiza@est.ipvce.lt.rimed.cu

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: Segment Tree en 2D

Postby isaac » Sun Nov 29, 2015 11:27 pm

A la verdad que es una idea superbuena. Ahora, el problema esta en que puede resultar bastante tediosa la implementacion. Quizas me equivoque pero sigo siendo partidario de la implementacion de este con una estructura autorreferenciada. Creo que el unico inconveniente es que el codigo es bastante complejo para el que no conoce ciertas cosillas del lenguaje y del trabajo con punteros, pero eso es muela. Este tipo de implementacion es incluso mas eficiente porque solamente se construyen los nodos sobre los cuales se va a trabajar en tiempo de ejecucion, no asi el caso de la implementacion normal.

User avatar
WIL
Posts: 11
Joined: Thu Dec 08, 2011 12:02 pm
Gender: Male

Re: Segment Tree en 2D

Postby WIL » Tue Feb 02, 2016 9:25 pm

La implementación del quatree q utilizo yo es realmente igual que la del segmentree lo q llevando 4 valores en cada nodo del arbol.
segmentree basico

Code: Select all

int tree[M*4],arb[M*4][2],arr[M],cant=0;
int create(int i,int f){
   int node=cant++;
   if(f-i==1){
      tree[node]=arr[i];
      return node;
   }
   int p=(i+f)/2;
   arb[node][0]=create(i,p);
   arb[node][1]=create(p,f);
   tree[node]=max(tree[arb[node][0]],tree[arb[node][1]]);
   return node;
}
int query(int node,int i,int f,int a,int b){
   if(i>=b || f<=a)return -oo;
   if(i>=a && f<=b)return tree[node];
   int p=(i+f)/2;
   return max(query(arb[node][0],i,p,a,b),query(arb[node][1],p,f,a,b));
}
int update(int node,int i,int f,int a,int b,int newvalue){
   //code
}


y si le agregamos otra dimención sería algo como:

Code: Select all

int tree[M*4],arb[M*4][4],arr[M],cant=0;
int create(int i,int f,int I,int F){
   int node=cant++;
   if(f-i==1 && F-I==1){
      tree[node]=arr[i][I];
      return node;
   }
   int p=(i+f)/2;
   int P=(I+F)/2;
   arb[node][0]=create(i,p,I,P);
   arb[node][1]=create(p,f,I,P);
   arb[node][2]=create(i,p,P,F);
   arb[node][3]=create(p,f,P,F);
   tree[node]=max( tree[arb[node][0]], max( tree[arb[node][1]], max( tree[arb[node][2]],tree[arb[node][3]] ) ) );
   return node;
}
int query(int node,int i,int f,int I,int F,int a,int b,int c,int d){
   if(i>=b || f<=a || I>=d || F<=c)return -oo;
   if(i>=a && f<=b && I>=c && F<=d)return tree[node];
   int p=(i+f)/2;
   int P=(I+F)/2;
   return max( query(arb[node][0],i,p,I,P,a,b,c,d), max( query(arb[node][1],p,f,I,P,a,b,c,d), max( query(arb[node][2],i,p,P,F,a,b,c,d), query(arb[node][3],p,f,P,F,a,b,c,d) ) ) );
}
int update(int node,int i,int f,int I,int F,int a,int b,int c,int d,int newvalue){
   //code
}


Más o menos por ahi anda la cosa, puede q se me halla quedado algún detalle en el code, solo lo puse como referencia para mostrar las pocas diferencias entre los métodos. El principal problema con el quatree es la memoria, dado q en problemas con una matriz muy grande, puede dar memory limit. ;) ;) ;) ;)
I'm interesting in learn!!!

User avatar
alurquiza
Posts: 55
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Re: Segment Tree en 2D

Postby alurquiza » Wed Feb 03, 2016 9:26 pm

Gracias por el code, yo lo implemento de otra forma:

Code: Select all

struct QuadTree{
    int A[SIZE * SIZE * 2],x1,x2,y1,y2,value;

    QuadTree(){
        memset(A,0,sizeof(A));
    }

    int query(int nodo,int f1,int c1,int f2,int c2){
        if(f1 > f2 || c1 > c2 || f2 < x1 || f1 > x2 || c2 < y1 || c1 > y2)
            return 0;
        if(x1 <= f1 && y1 <= c1 && c2 <= y2 && f2 <= x2)
            return A[nodo];

        int mit1 = (f1 + f2) >> 1;
        int mit2 = (c1 + c2) >> 1;

        int r = 0;
        r += query(nodo * 4 - 2,f1,c1,mit1,mit2);
        r += query(nodo * 4 - 1,f1,mit2 + 1,mit1,c2);
        r += query(nodo * 4,mit1 + 1,c1,f2,mit2);
        r += query(nodo * 4 + 1,mit1 + 1,mit2 + 1,f2,c2);

        return r % MOD;
    }

    void update(int nodo,int f1,int c1,int f2,int c2){
        if(x1 > N || y1 > N || x1 < 1 || y1 < 1)
            return;
        if(f1 > f2 || c1 > c2 || f2 < x1 || f1 > x1 || c2 < y1 || c1 > y1)
            return;
        if(x1 == f1 && y1 == c1 && f1 == f2 && c1 == c2){
            A[nodo] += value;
            A[nodo] %= MOD;
            return;
        }

        int mit1 = (f1 + f2) >> 1;
        int mit2 = (c1 + c2) >> 1;

        update(nodo * 4 - 2,f1,c1,mit1,mit2);
        update(nodo * 4 - 1,f1,mit2 + 1,mit1,c2);
        update(nodo * 4,mit1 + 1,c1,f2,mit2);
        update(nodo * 4 + 1,mit1 + 1,mit2 + 1,f2,c2);

        A[nodo] = 0;
        for(int i = -2;i <= 1;i++)
            A[nodo] += A[nodo * 4 + i];
        A[nodo] %= MOD;
    }

}QT;


Ahi esta enredada un poco de gente, incluso yo cuando quise aprender, que confunden el Segment Tree en 2D con el Quad Tree. Son dos ideas totalmente distintas. El Quad Tree genera cuatro nodos hijos, mientras que el Segment Tree en 2D tiene un Segment Tree en cada nodo de otro Segmet Tree. El codigo que puse alla arriba es de un Quad Tree, no un Segmet Tree 2D.


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest