Contestaré mi propia pregunta. Se encontró una manera de hacer esto en [math] O (n \ log n) [/ math] time y [math] O (n) [/ math] memoria adicional.
Asumiré sin pérdida de generalidad que estamos tratando con un árbol binario.
Además, considere que la magnitud de los valores del nodo de árbol es [matemática] O (n) [/ matemática]. Si no, use una de las estrategias descritas al final (*).
Cree un árbol indexado binario auxiliar (BIT) y realice un recorrido de orden posterior del árbol dado para actualizar. Para cada nodo
- ¿Qué tipo de preguntas se hacen para la ingeniería automotriz en VIT para VITMEE? ¿Me puede dar algunas preguntas de muestra?
- ¿Qué bootcamp de codificación requiere codificación o entrevistas técnicas para sus aplicaciones?
- ¿Cuál es la estructura de datos y UX requerida para buscar fácilmente el contenido de Quora? ¿Qué se necesitaría para presentar esto de una manera simple y requerir el tiempo mínimo de lectura?
- ¿Cómo son las entrevistas de ingeniería de software de Google Hyderabad?
- Cómo mejorarme siendo un graduado de TI más fresco, para poder descifrar las entrevistas técnicas redondas de Java
- Calcule la suma de los valores insertados en el BIT que son menores que el valor del nodo actual. Llame a esto sum_before.
- Actualice los hijos de este nodo de forma recursiva y reutilice el BIT actual.
- Agregue el valor del nodo actual al BIT.
- Actualice el valor del nodo actual a la suma de valores en el BIT menor que el valor actual – sum_before.
El BIT solo contendrá valores en el árbol original. Además, al guardar sum_before , descartamos los valores agregados en otras ramas del árbol, considerando solo los valores agregados en el subárbol del nodo actual.
Para cada nodo, hacemos dos operaciones de Lectura y una de Actualización en el BIT. Cada uno toma [math] O (\ log n) [/ math]. Entonces, la complejidad de tiempo general del algoritmo es [matemática] O (n \ log n) [/ matemática]. El BIT utiliza memoria adicional [matemática] O (n) [/ matemática].
Implementación de muestra en C ++:
struct BITree {
vector tree;
int size; BITree(int n = 10) : tree(vector(n, 0)), size(n) {} void Update(int x, int value) {
for (; x < size; x += x & -x)
tree[x] += value;
}
int Read(int x) {
int sum = 0;
for (; x > 0; x -= x & -x)
sum += tree[x];
return sum;
}
}; void TreeUpdate(Node* cur, BITree* bit) {
if (!cur)
return;
int sum_before = bit->Read(cur->value-1);
TreeUpdate(cur->left, bit);
TreeUpdate(cur->right, bit);
bit->Update(cur->value, cur->value);
cur->value = bit->Read(cur->value-1) - sum_before;
}
struct BITree {
vector tree;
int size; BITree(int n = 10) : tree(vector(n, 0)), size(n) {} void Update(int x, int value) {
for (; x < size; x += x & -x)
tree[x] += value;
}
int Read(int x) {
int sum = 0;
for (; x > 0; x -= x & -x)
sum += tree[x];
return sum;
}
}; void TreeUpdate(Node* cur, BITree* bit) {
if (!cur)
return;
int sum_before = bit->Read(cur->value-1);
TreeUpdate(cur->left, bit);
TreeUpdate(cur->right, bit);
bit->Update(cur->value, cur->value);
cur->value = bit->Read(cur->value-1) - sum_before;
}
struct BITree {
vector tree;
int size; BITree(int n = 10) : tree(vector(n, 0)), size(n) {} void Update(int x, int value) {
for (; x < size; x += x & -x)
tree[x] += value;
}
int Read(int x) {
int sum = 0;
for (; x > 0; x -= x & -x)
sum += tree[x];
return sum;
}
}; void TreeUpdate(Node* cur, BITree* bit) {
if (!cur)
return;
int sum_before = bit->Read(cur->value-1);
TreeUpdate(cur->left, bit);
TreeUpdate(cur->right, bit);
bit->Update(cur->value, cur->value);
cur->value = bit->Read(cur->value-1) - sum_before;
}
struct BITree {
vector tree;
int size; BITree(int n = 10) : tree(vector(n, 0)), size(n) {} void Update(int x, int value) {
for (; x < size; x += x & -x)
tree[x] += value;
}
int Read(int x) {
int sum = 0;
for (; x > 0; x -= x & -x)
sum += tree[x];
return sum;
}
}; void TreeUpdate(Node* cur, BITree* bit) {
if (!cur)
return;
int sum_before = bit->Read(cur->value-1);
TreeUpdate(cur->left, bit);
TreeUpdate(cur->right, bit);
bit->Update(cur->value, cur->value);
cur->value = bit->Read(cur->value-1) - sum_before;
}
(*) Si los valores pueden ser negativos o mucho mayores que n, podemos hacer un paso de preprocesamiento para asignar cada valor a un número entero en el rango [1, n]. Podemos hacer esto agregando todos los valores en una matriz, ordenándolos y luego usando un mapa hash.
Otra opción es extender un árbol de búsqueda binario balanceado o un árbol de segmentos que permita consultar la suma de valores hasta X.