Árbol de Fenwick

El Árbol de Fenwick (también conocido como Árbol Binario Indexado o BIT por sus siglas en ingles) fue propuesto por Peter M Fenwick en 1994 para resolver problemas de compresión de datos. Es una estructura de datos muy eficiente para calcular sumas acumulativas. Para ilustrar el concepto de esta estructura, vamos a definir el siguiente problema:

Disponemos de n alcancias y varias monedas de distintos valores. Podemos insertar una moneda con cualquier valor en cualquiera de las alcancias, y estamos interesados en calcular la cantidad total de dinero que tenemos acumulada desde la alcancia 1 hasta la alcancia i.

bit_problem

Una forma de resolver este problema seria recorriendo cada alcancia desde 1 hasta i y sumar todos los valores para obtener la suma total, pero esta solucion es muy lenta cuando tenemos muchas alcancias. El BIT permite solucionar este problema de forma mas eficiente. Para solucionarlo, definiremos un arbol donde habran nodos responsables, y nodos dependientes.

Cada nodo responsable se encarga de mantener la suma de los valores de todos sus nodos dependientes. De esta manera, para calcular una suma en cualquier intervalo solo hay que tomar los valores en los nodos responsables que estén en el intervalo, y sumarlos, ya que estos comprimen en ellos la información de sus nodos dependientes.

Como determinar si un nodo es responsable o dependiente? Para esto definimos la función lowbit(i), la cual nos dice dado un numero i cual es el menor bit que tiene valor 1 en la representación binaria de este numero. Por ejemplo, el numero 6 es 110 en binario (1×2^2 + 1×2^1 + 0×2^0), y su menor bit es 1×2^1 = 2. Esto se puede calcular de la siguiente forma:

1
public int lowbit(int i) { return (i & -i); }

Este árbol puede ser representado implícitamente  asumiendo cada elemento original como un nodo en el árbol. Cada elemento i sera responsable por los elementos entre las posiciones i-lowbit(i)+1 hasta i, y almacenara el valor de la suma de los elementos en ese intervalo. Por ejemplo, lowbit(6)=2, por tanto, el elemento en la posición 6 es responsable por el elemento 5 y 6, y en el problema original, el valor seria la suma de la alcancia 5 + la suma de la alcancia 6. En el caso de 8, lowbit(8) = 8, y el elemento 8 seria responsable por los valores de las alcancias desde 1 hasta la 8.

Supongamos que los valores de las alcancías de la 1 hasta la 8 son [2, 3, 1, 1, 5, 6, 0, 1], respectivamente. En la siguiente figura podemos ver los elementos responsables y dependientes, y sus valores:

Árbol de Fenwick construido a partir de los valores

Obtener la suma acumulada

Dada una posición i, podemos usar el árbol de Fewick para obtener la suma de los valores acumulados desde la alcancía 1 hasta la alcancía i-esima. Esto es A[1] + A[2] + … + A[i]. La forma de hacer esto es comenzar en la posición i, y tomar los valores de los elementos responsables del árbol hasta llegar a 1.

NOTA: El árbol de Fenwick siempre comienza en la posición 1.

1
2
3
4
5
6
public int sum(int i)
{
    int value = 0;
    for(; i > 0; i-= lowbit(i)) value+= T[i];
    return value;
}

De forma similar, es posible que necesitemos la suma de los valores acumulados de la alcancia i hasta la j (i < j). Esto es A[i] + A[i+1] + … + A[j]. Esto lo podemos calcular haciendo sum(j) – sum(i-1), ya que el resultado de esto seria:

A[1] + A[2] + … + A[i-1] + A[i] + A[i+1] + … + A[j] – (A[1] + A[2] + … + A[i-1]) = A[i] + A[i+1] + … + A[j].

1
2
3
4
public int sum(int i, int j)
{
    return i > 1 ? sum(j) - sum(i-1) : sum(j);
}

Igualmente podríamos estar interesados en el valor actual en la alcancía i, o sea, no en la suma de los valores acumulados desde la alcancía 1 hasta la i-esima, sino solamente el valor en esa alcancía. Esto lo podemos calcular fácilmente como sum(i) – sum(i-1).

Actualizar las cantidades

En este caso queremos agregar una moneda con valor v a la i-esima alcancía. También podemos sacar monedas de la i-esima alcancía.

Para esto, cambiamos el valor en el i-esimo elemento del árbol  y debemos notificar a todos los elementos que son responsables de el que ha ocurrido un cambio en el valor. Por ejemplo, si agregáramos una moneda en la alcancía 2, tendríamos que notificar a la 4 y a la 8 de este cambio  ya que ambas son responsables por la 2. Esto mantiene el árbol sincronizado. La forma de hacerlo es actualizar el valor en la posición i, y moverse hacia adelante en el árbol a todos los responsables haciéndoles saber que el elemento fue actualizado.

1
2
3
4
public void update(int i, int value)
{
    for(; i < T.length; i+= lowbit(i)) T[i] += value;
}

En caso de que estemos agregando una moneda con valor v, el valor de value sera positivo. Si estamos sacando una cantidad v, el valor sera negativo.

Construir el árbol

Ya hemos visto como hacer las operaciones fundamentales con el árbol de Fenwick, pero no hemos visto como construirlo! Precisamente el árbol se construye a partir de la operación update.

1
2
3
4
5
public void build(int[] A)
{
    int[] T = new int[A.length + 1];
    for(int i=0; i < A.length; i++) update(i+1, A[i]);
}

Y esto es todo, amigos. El árbol de Fenwick es una estructura muy eficiente, sin embargo sencilla. El concepto no es difícil de entender, y aun sin comprenderlo totalmente, con solo saber como utilizarla, podemos resolver muchísimos problemas. Ademas, se puede extender con facilidad a problemas de varias dimensiones, pero vamos a dedicar otro post completamente a ese tema.

Felices códigos!

Referencias

es.wikipedia.org/wiki/%C3%81rbol_binario_indexado

olds.blogcn.com/wp-content/uploads/67/6754/2009/01/bit.pdf

community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

comeoncodeon.wordpress.com/2009/09/17/binary-indexed-tree-bit/

www.algorithmist.com/index.php/Fenwick_tree

www.swageroo.com/wordpress/little-known-awesome-algorithms-fenwick-range-trees-rapidly-find-cumulative-frequency-sums/

gborah.wordpress.com/2011/09/24/bit-indexed-tree-fenwick-tree/

Problemas

spoj.pl/problems/INVCNT/

www.spoj.com/problems/YODANESS/

uva.onlinejudge.org/external/119/11926.pdf

uva.onlinejudge.org/external/115/11525.pdf

coj.uci.cu/24h/problem.xhtml?abb=1850

coj.uci.cu/24h/problem.xhtml?abb=2125

Visto en http://prodeportiva.wordpress.com

Post to Twitter

Posted in Concursos de Programación, Estructuras de datos, Programacion, Técnicas de programación | Tagged , , , , , | Leave a comment

Comienza la primera ronda del Google Code Jam

logo_image1

Hoy ha comenzado la primera ronda del Google Code Jam. Google Code Jam es un concurso de programación organizado por Google donde puede participar cualquiera. El concurso puede realizarse usando cualquier lenguaje de programación, ya que el concurso lo que hace es enviarte sus juegos de prueba y tu envias el resultado y el codigo fuente utilizado, sin importar el lenguaje utilizado ya que la ejecución se realiza en tu máquina.

Podeis acceder a través de http://code.google.com/codejam

Para intentar pasar esta primera ronde previa, tenéis de tiempo hasta el 13 de abril a las 02:00 UTC (04:00 hora española). Hay que conseguir al menos 25 puntos para clasificarse para la siguiente ronda.

Yo estoy participando, os animo a todos a participar y a comentar vuestras impresiones.

Post to Twitter

Posted in Concursos de Programación, Programacion | Leave a comment

ProgramaMe 2014: resultados del segundo regional online (Zona norte)

Se ha publicado en http://www.programa-me.com/2014/reg/ourense/ los resultados del ProgramaMe 2014: primer regional online, realizado en el CIFP A Carballeira-Marcos Valcárcel.de Ourense.

Los clasificados directos para la final de ProgramaMe 2014 son los 3 primeros clasificados. El cuarto clasificado debe que esperar a la comprobación de la clasificación de todas las sedes.

Centro Logo Equipo
IES Pedro Mercedes (Cuenca) Logo IES Pedro Mercedes - Cuenca Read Write eXecute
IES Muralla Romana (Lugo) Logo IES Muralla Romana - Lugo Cuatrisquel
Colegio Santísima Trinidad (Salamanca) Logo Colegio Santísima Trinidad - Salamanca Trinteam

Post to Twitter

Posted in Concursos de Programación, Programacion, ProgramaMe | Tagged , , , , , | Leave a comment

Segundo concurso clasificatorio para la final de la OIE

Mañana 2 de abril se realiza el segundo concurso clasificatorio para la OIE (Olimpiada Informática Española).

Tenéis todas la información aqui http://olimpiada-informatica.org/

Desde aqui deseamos muchas suerte a todos los participantes.

Post to Twitter

Posted in OIE, Programacion | Tagged , , , , , , | Leave a comment

ProgramaMe 2014: resultados del primer regional online (Zona sur)

Se ha publicado en http://www.programa-me.com/2014/reg/torrent/ los resultados del ProgramaMe 2014: primer regional online, realizado en el IES Serra Perenxisa de Torrent (Valencia).

Los equipos clasificados para la final nacional han sido:

IES Henri Matisse matisse 2 (Primer clasificado)
IES San Vicente Booleano (Segundo clasificado)
IES Albarregas El equipo B (Tercer clasificado)

Habrá que esperar a los resultados del resto de competiciones para conocer si habrá un cuarto equipo clasificado.

El segundo regional online de Ourense http://www.programa-me.com/2014/reg/ourense/index.php se realizará el jueves 3 de abril. Estaremos atentos a los resultados.

Post to Twitter

Posted in Concursos de Programación, ProgramaMe | Tagged , , , , , , , , , , , , | Leave a comment

Giro del portal hacia los concursos de programación

El portal Hispabyte.net ha decidido dar un giro en su temática y centrarse en la temática relacionada con la programación en general y en particular con los concursos de programación.

El portal se hará eco de:

  • Noticias relacionadas con los concursos de programación, tanto a nivel nacional como a nivel internacional.
  • Publicación de técnicas, manuales, libros, etc… relacioandos con los concursos de programación.

Se seguirá de forma muy especial las competiciones de programación nacionales:

Además se han remodelado los foros para dar cabidas a intercambios de conocimiento relacionados exclusivamente con la programación y los concursos de programación.

Esperemos disfruteis del giro del site.

Post to Twitter

Posted in Concursos de Programación, Programacion | Leave a comment

Computer History publica el código fuente del MS-DOS y del Word

Computer History ha obtenido el permiso de Microsoft para poder publicar el código fuente de las primeras versiones de MS-DOS y de Word.

En aquél entonces el programa ofimático por excelencia era el mítico WordPerfect.

El Word, en el año 1989 con su salida para Windows conseguiría darle la vuelta a la tortilla y desplazar el WordPerfect del mercado.

Estos códigos que ha cedido Microsoft no se pueden utilizar para crear versiones ni productos derivados. Se trata de tan sólo una contribución curiosa que preservará una parte de la historia de la informática.

Enlace a Computer History http://www.computerhistory.org/press/ms-source-code.html

Post to Twitter

Posted in Programacion, Sistemas Operativos, Software, sysadmin | Tagged | Leave a comment

Profesores jubilados crean una plataforma online con material didáctico

Un grupo de profesores jubilados ha creado una plataforma online que facilita tanto a docentes como a familias, material didáctico libre y gratuito, en un momento en el que se prevé un cambio en algunos libros por la entrada en vigor de la nueva ley de educación.

A través de esta herramienta, Educatribu http://www.educatribu.net/ , una maestra de Educación Infantil podrá subir una unidad didáctica para desarrollar un proyecto con niños de tres años; un profesor de Secundaria podrá colgar ejercicios de repaso de inglés, y otro de Bachillerato, comentarios de texto sobre una obra determinada.

También proporcionará aplicaciones para tablet; podcast; audios o vídeos y juegos interactivos para pizarras digitales que podrán ser descargadas por todo aquel interesado sin necesidad de registrarse, ha indicado uno de sus creadores, Virgilio Marco, antiguo profesor del instituto Tiempos Modernos de Zaragoza.

Post to Twitter

Posted in Hispabyte, Noticias, Redes sociales, Tutoriales / Manuales | Leave a comment

Antivirus gratuitos y portables

A continuación proporcionamos algunos enlaces a antivirus portables. Como administradores puede ser muy útil llevarlos en un pen o similar.

ClamWin Antivirus Portable

Este antivirus es gratuito, de código abierto s. Muy conocido dentro de los sistemas informáticos (disponible para WIndows y Linux), ClamWin tiene un prestigio a la altura de cualquier solución de pago.

Pagina Oficial

Kaspersky Virus Removal Tool

Kaspersky Virus Removal Tool nos permite limpiar de todo tipo de malware nuestro ordenador fácilmente utilizando la conocida base de datos de la empresa Kaspersky que tan buenos resultados de detección reporta.

Pagina Oficial

Dr.Web CureIt!

La principal característica de este antivirus gratuito y portables es la posibilidad de elegir las diferentes categorías que queremos analizar.

Pagina oficial

 

Post to Twitter

Posted in Seguridad, Virus / Troyanos | Tagged , , , , | Leave a comment

Warrior Pride, el spyware de los servicios de inteligencia para acceder a tu teléfono

Su nombre es Warrior Pride y, al menos en 2010, que es de cuando data la presentación filtrada por Snowden, era capaz de activar un teléfono que estaba aparentemente apagado, utilizar su micrófono para escuchar conversaciones a distancia, localizarnos a través del GPS o recuperar cualquier contenido del mismo incluyendo “SMS, MMS, correos electrónicos, historial de navegación, llamadas recientes, vídeos, fotos, agenda, notas, calendarios”… Según la presentación de esta herramienta de spyware, “si está en el teléfono, podemos cogerlo”.

Probablemente los agujeros de seguridad que permitían funcionar a Warrior Pride fuesen cerrados en cualquiera de las actualizaciones de iOS y Android de los últimos tres años pero también es más que posible que con un presupuesto de 1.000 millones de dólares (cerca de 732 millones de euros), solo en el caso de la NSA y para esta materia en concreto, nuevos agujeros sean detectados y aprovechados con bastante más velocidad y discreción que la de nuestros amigos de la escena jailbreak.

Post to Twitter

Posted in Hardware, Movil | Tagged , , , , | Leave a comment