consultas

Fenwick tree

Fenwick tree es una estructura de datos que usa el manejo de bits para desplazarse entre los nodos de un arbol, permitiendo responder consultas en una complejidad $O$(log n) mediante la idea de expresar la suma a[1] + a[2] + ... + a[n], en sumas acumuladas del mismo tamaño que la suma de potencias de 2 que forman n.

ejemplo:

a[1] + a[2] + ... + a[21] = (a[1] + a[2] + ... + a[16])  +  (a[17] + ... + a[20]) + (a[21])


requisitos de función:

1. para sumas en rangos: grupo
2. para sumas desde el origen: semi grupo

código:


ejercicios y tutoriales:

Tabla de esparción

La tabla de esparción es una estructura de datos en la cual guardamos la respuesta en los rangos

[i, $i + 2^k$), de tal forma que para construir la tabla tenemos:

si k es igual a 0: f{[i, i+1)} = a[i]

en otro caso: f{[i, $i + 2^k$)} = f{f{[i, i $+ 2^{k-1}$)}, f{[$i+2^{k-1}$, $i + 2^{k-1} + 2^{k-1}$)} 

requisitos de función:

1. para sumas en rangos: funciones aritméticas que cumplan f(x, f(x, y)) = f(x, y)

2. con algunas modificaciones solo se necesita un semi grupo.

código:

Segment tree

Segment tree es de las estructura de datos tipo árbol más útiles, no solo permite hacer actualizaciones en indices, consultas en rango y construcciones en $O$(n), además permite ajustarla para hacer actualizaciones en rango, además que su versión persistente es aún más de versátil. Segment tree es uno de los más claros ejemplos del paradigma Divide and Conquer, en esta estructura de datos encontraremos dos funciones clave: merge y split, la primera servirá para juntar dos conjuntos disjuntos y la segunda para propagar la información retenida en los nodos.

requisitos de funcion:

1. semigrupo.

código:

Sqrt Descomposition

Sqrt descomposition es un método para resolver problemas con querys en el cual buscaremos dividir los procesos en tamaños igualas a la raiz del array.

requisitos de función:

1. en general semigrupo pero para optimizar las consultas es preferible un grupo.

código:

Mo's algorithm

El algoritmo de Mo es un algoritmo estructura de datos que particiona las consultas respecto en que bloque se encuentran (array particionado en sqrt(n) bloques) al lado final del rango.

requisitos de función:

1. semigrupo.

codigo:

Centroid descomposition

Centroid descomposition es un algoritmo que consiste en particionar recursivamente un árbol por uno de sus centroides y asi minimizar el costo de las operaciones

requisitos de función:

1. semigrupo

código: