Entonces estaba tratando de resolver este problema de programación.

Dada una serie de números y algunas consultas. Cada consulta le da tres números a, b, c y le pide que responda la suma de todos los elementos del índice a al índice b (ambos incluidos) que son menores o iguales que c.

por ejemplo:

Conjunto dado: {2,4,6,1,5,1,6,4,5,4}

Se deben responder 3 consultas:

2 4 4 -> ans = 5 es decir {4 + 1}

1 5 3 -> ans = 3 es decir, {2 + 1}

4 5 1 -> ans = 1

cada valor en la matriz es inferior a 10 ^ 5, la longitud de la matriz y el número de consultas pueden variar hasta 10 ^ 5

Esto es lo que hice. Utilicé el algoritmo de Mo (descomposición de raíz cuadrada) para ordenar las consultas, y creé un árbol indexado binario para almacenar la suma acumulativa de los elementos menos que todos los valores de 1-10 ^ 5, e hice una actualización desde consultas a consultas. Con este algoritmo, la complejidad general de mi solución es O (q * sqrt (N) * log (N)) pero no es lo suficientemente rápido. Estaba buscando un mejor algoritmo. Creo que la descomposición de consultas de raíz cuadrada no funcionaría. ¿Hay algún algoritmo mejor para resolver este problema?

Me preguntaba si alguna estructura de datos podría resolver este problema que desconozco.