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.
Post Reply
User avatar
alurquiza
Posts: 54
Joined: 3 years ago
Gender: Male

Segment Tree en 2D

Post by alurquiza » 3 years ago

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: 3 years ago
Gender: None specified

Re: Segment Tree en 2D

Post by isaac » 3 years ago

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: 54
Joined: 3 years ago
Gender: Male

Re: Segment Tree en 2D

Post by alurquiza » 3 years ago

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: 54
Joined: 3 years ago
Gender: Male

Re: Segment Tree en 2D

Post by alurquiza » 3 years ago

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: 3 years ago
Gender: None specified

Re: Segment Tree en 2D

Post by isaac » 3 years ago

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: 7 years ago
Gender: Male

Re: Segment Tree en 2D

Post by WIL » 2 years ago

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: 54
Joined: 3 years ago
Gender: Male

Re: Segment Tree en 2D

Post by alurquiza » 2 years ago

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.

Post Reply

Return to “Algorithms”