Segment Tree en 2D

[alurquiza]

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.

[isaac]

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.

[alurquiza]

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.

[alurquiza]

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

[isaac]

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.

[WIL]

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.

[alurquiza]

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.