Cómo resolver la consulta de suma de potencia de rango usando treap

No estoy en SPOJ, no veo este problema antes, a continuación solo estoy adivinando al leer la declaración del problema.

El punto # 4 en cuestión, la consulta lrk indirectamente requiere una suma de L a R. Eso se puede hacer por hecho conocido estándar de suma [1 a R] menos suma [1 a L-1] o similar.

Lo anterior requiere la suma del prefijo de valores grandes de una gran cantidad de nodos. Por lo tanto, es mejor tener algunas sumas almacenadas en varios nodos. Pero nuevamente tiene operaciones de eliminación e inserción en la pregunta, por lo que realmente dudo si Treap es un buen DS basado en operaciones que admite, que eché un vistazo rápido: Treap, solo son insertar, eliminar, buscar, dividir, fusionar /Unión.

• Noto que las estructuras de datos son difíciles de entender y asimilar con solo leerlas. ¿Qué tengo que hacer?
• ¿Cuántos números debajo de [matemática] 10 ^ n [/ matemática] hay cuyos dígitos suman [matemática] [/ matemática]?
• ¿Cuáles son algunos URI de buen código de ejemplo que utilizan algoritmos STL (aparte de la ordenación)?
• ¿El uso de una función recursiva en el código aumenta mucho el tiempo de ejecución?
• ¿Qué son los algoritmos y la estructura de datos y cómo puedo comenzar con ellos?

Si es posible, mire el árbol Fenwick o el árbol de segmentos

1. Para el árbol Fenwick, como recuerdo, la actualización se puede usar para insertar, no recuerdo que hubo una eliminación, puede hacer lo mismo o hacer un poco de trabajo inteligente.
1. La estructura de nodos para Fenwick es simplemente almacenar la suma que tiene, en cada nodo. Pero esta pregunta parece ser un poco inteligente al incluir el valor i en la suma. Pero si piensas lo suficiente, encontrarás una solución.
2. Para el árbol de segmentos, aquí nuevamente, no recuerdo la operación de eliminación, especialmente la wikipedia dice “Es, en principio, una estructura estática; es decir, su estructura no se puede modificar una vez que está construida ”, por lo que una operación de eliminación nuevamente necesitará un poco de trabajo inteligente.

Fenwick se ve un poco mejor, pero Sumod Mathilakath dice que el árbol de segmentos, prueba y ve qué se ajusta correctamente

Si todo lo demás falla, lo que parece poco probable, tome una pista del tipo Top 30 en SPOJ, que es un amigo mío. Para esto, hágame ping en los comentarios, después de intentarlo lo suficiente.

la mejor de las suertes.