Modifiquemos un poco el problema …
Suponga que en lugar de agregar elementos al comienzo de la matriz, los agrega al final. ¿Cómo podrías responder las preguntas? Bueno, si mantiene una matriz de suma de prefijo, puede responder la consulta de suma con Sum [r] – Sum [l-1], y la consulta de actualización agregando el nuevo prefijo a su matriz con Sum [N + 1] = Sum [ N] + elemento, y luego aumentando N para el nuevo tamaño. Ambos te llevan O (1) tiempo.
Entonces, ¿cómo puedes transformar el problema original en este? Bueno, mantenga la matriz invertida :). Entonces, agregar al comienzo de la matriz original es equivalente a agregar al final de la matriz invertida, y la consulta de suma (l, r) en la matriz original es equivalente a hacer una suma (N-r + 1, N-l +1) en la matriz invertida (para ver por qué funciona esto, solo vea que el primer elemento se asigna al elemento Nth, el segundo al N-1th y así sucesivamente).
- ¿Cómo podemos calcular el factorial de los primeros N números naturales usando la metaprogramación de plantilla en C ++?
- ¿Es posible aprender automáticamente los diferentes métodos y algoritmos de aprendizaje automático?
- Según usted, ¿cuáles son los algoritmos de aprendizaje automático más importantes en la actualidad?
- ¿Hay algún algoritmo que pueda implementarse en un lenguaje de programación pero no en otro lenguaje de programación?
- ¿Dónde puedo encontrar a alguien dispuesto a enseñarme estructura de datos y algoritmos de forma gratuita o a un costo muy barato?
Espero que ayude!
