Prerrequisitos: Árbol de segmentos
Dado un número N que representa el tamaño de la array inicializada en 0 y Q consultas para procesar donde hay dos tipos de consultas:
- 1 PV: Ponga el valor V en la posición P .
- 2 LR: salida de la suma de valores de L a R .
La tarea es responder a estas consultas.
Restricciones:
- 1 ≤ norte ≤ 10 18
- Q ≤ 10 5
- 1 ≤ L ≤ R≤ norte
Nota: Las consultas son en línea. Por lo tanto:
- L = (respuesta anterior + L) % N + 1
- R = (respuesta anterior + R) % N + 1
Ejemplos:
Entrada: N = 5, Q = 5, arr[][] = {{1, 2, 3}, {1, 1, 4}, {1, 3, 5}, {1, 4, 7}, { 2, 3, 4}}
Salida: 12
Explicación:
Hay cinco consultas. Dado que N = 5, por lo tanto, inicialmente, la array es {0, 0, 0, 0, 0}
Para la consulta 1: 1 2 3 array = {0, 3, 0, 0, 0}
Para la consulta 2: 1 1 4 array = {4, 3, 0, 0, 0}
Para la consulta 3: 1 3 5 array = {4, 3, 5, 0, 0}
Para la consulta 4: 1 4 7 array = {4, 3, 5, 7 , 0}
Para la consulta 5: 2 3 4 Suma de [3, 4] = 7 + 5 = 12.Entrada: N = 3, Q = 2, arr[][] = {{1, 1, 1}, {1, 2, 2}, {1, 3, 3}}
Salida: 0
Enfoque: aquí, dado que las actualizaciones son altas, el algoritmo de Kadane no funciona del todo bien. Además, dado que las consultas son en línea, un simple árbol de segmentos no podría resolver este problema porque las restricciones por el número de elementos son muy altas. Por lo tanto, en este problema se utiliza un nuevo tipo de estructura de datos, un árbol de segmento dinámico.
Árbol de segmentos dinámicos: el árbol de segmentos dinámicos no es una nueva estructura de datos. Es muy similar al árbol de segmentos . Las siguientes son las propiedades del árbol de segmentos dinámicos:
- En lugar de usar una array para representar los intervalos, se crea un Node cada vez que se actualiza un nuevo intervalo.
- La siguiente es la estructura del Node del árbol de segmentos dinámicos:
C++
// Every node contains the value and
// the left subtree and right subtree
struct Node {
long long value;
struct Node *L, *R;
};
struct Node* getnode()
{
struct Node* temp = new struct Node;
temp->value = 0;
temp->L = NULL;
temp->R = NULL;
return temp;
}
- Claramente, la estructura anterior es la misma que un árbol de búsqueda binaria . En cada Node, estamos almacenando el valor del Node y dos punteros que apuntan al subárbol izquierdo y derecho.
- El Intervalo de la raíz es desde [1, N], el intervalo del subárbol izquierdo será [1, N/2] y el intervalo del subárbol derecho será [N/2 + 1, N].
- De manera similar, para cada Node, podemos calcular el intervalo que representa. Digamos que el intervalo del Node actual es [L, R]. Entonces, el Intervalo de su subárbol izquierdo y derecho son [L, (L + R)/2] y [(L + R)/2+1, R] respectivamente.
- Dado que estamos creando un nuevo Node solo cuando es necesario, la función build() del árbol de segmentos se elimina por completo.
Antes de entrar en el algoritmo de las operaciones, definamos los términos utilizados en este artículo:
- Intervalo del Node: Es el intervalo que representa el Node.
- Intervalo requerido: Intervalo para el cual se va a calcular la suma.
- Índice requerido: índice en el que se requiere actualización.
El siguiente es el algoritmo utilizado para las operaciones sobre el árbol con las propiedades antes mencionadas:
- Actualización de puntos: El siguiente algoritmo se utiliza para la actualización de puntos:
- Comience con el Node raíz.
- Si el intervalo en el Node no se superpone con el índice requerido, regrese.
- Si el Node es una entrada NULL, cree un nuevo Node con los intervalos apropiados y descienda a ese Node volviendo al paso 2 para cada nuevo hijo creado.
- Si tanto los intervalos como el índice en el que se va a almacenar el valor son iguales, almacene el valor en ese Node.
- Si el intervalo en el Node se superpone parcialmente con el índice requerido, descienda a sus hijos y continúe la ejecución desde el paso 2.
- Encontrar la suma para cada consulta: El siguiente algoritmo se utiliza para encontrar la suma para cada consulta:
- Comience con el Node raíz.
- Si el Node es NULL o el intervalo en ese Node no se superpone con el intervalo requerido, devuelva 0.
- Si el intervalo en el Node se superpone completamente con el intervalo requerido, devuelva el valor almacenado en el Node.
- Si el intervalo en el Node se superpone parcialmente con el intervalo requerido, descienda a sus hijos y continúe la ejecución desde el paso 2 para ambos hijos.
Ejemplo: Permite visualizar la actualización y la suma con un ejemplo. Sea N = 10 y las operaciones necesarias para realizar en el árbol son las siguientes:
- Inserte 10 en la posición 1.
- Encuentra la suma de los valores de los índices de 2 a 8.
- Inserte 3 en la posición 5.
- Encuentra la suma de los valores de los índices de 3 a 6.
- Inicialmente, para el valor N = 10, el árbol está vacío. Por lo tanto:
- Inserte 10 en la posición 1. Para hacer esto, cree un nuevo Node hasta que obtengamos el intervalo requerido. Por lo tanto:
- Encuentre la suma del valor de los índices de 2 a 8. Para hacer esto, se encuentra la suma de [1, 8] y se le resta el valor [1, 2]. Dado que el Node [1, 8] aún no se ha creado, el valor de [1, 8] es el valor de la raíz [1, 10]. Por lo tanto:
- Inserte 3 en la posición 5. Para hacer esto, cree un nuevo Node hasta que obtengamos el intervalo requerido. Por lo tanto:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the implementation
// of the Dynamic segment tree and
// perform the range updates on the
// given queries
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Structure of the node
struct Node {
ll value;
struct Node *L, *R;
};
// Structure to get the newly formed
// node
struct Node* getnode()
{
struct Node* temp = new struct Node;
temp->value = 0;
temp->L = NULL;
temp->R = NULL;
return temp;
}
// Creating the Root node
struct Node* root;
// Function to perform the point update
// on the dynamic segment tree
void UpdateHelper(struct Node* curr, ll index,
ll L, ll R, ll val)
{
// If the index is not overlapping
// with the index
if (L > index || R < index)
return;
// If the index is completely overlapping
// with the index
if (L == R && L == index) {
// Update the value of the node
// to the given value
curr->value = val;
return;
}
// Computing the middle index if none
// of the above base cases are satisfied
ll mid = L - (L - R) / 2;
ll sum1 = 0, sum2 = 0;
// If the index is in the left subtree
if (index <= mid) {
// Create a new node if the left
// subtree is is null
if (curr->L == NULL)
curr->L = getnode();
// Recursively call the function
// for the left subtree
UpdateHelper(curr->L, index, L, mid, val);
}
// If the index is in the right subtree
else {
// Create a new node if the right
// subtree is is null
if (curr->R == NULL)
curr->R = getnode();
// Recursively call the function
// for the right subtree
UpdateHelper(curr->R, index, mid + 1, R, val);
}
// Storing the sum of the left subtree
if (curr->L)
sum1 = curr->L->value;
// Storing the sum of the right subtree
if (curr->R)
sum2 = curr->R->value;
// Storing the sum of the children into
// the node's value
curr->value = sum1 + sum2;
return;
}
// Function to find the sum of the
// values given by the range
ll queryHelper(struct Node* curr, ll a,
ll b, ll L, ll R)
{
// Return 0 if the root is null
if (curr == NULL)
return 0;
// If the index is not overlapping
// with the index, then the node
// is not created. So sum is 0
if (L > b || R < a)
return 0;
// If the index is completely overlapping
// with the index, return the node's value
if (L >= a && R <= b)
return curr->value;
ll mid = L - (L - R) / 2;
// Return the sum of values stored
// at the node's children
return queryHelper(curr->L, a, b, L, mid)
+ queryHelper(curr->R, a, b, mid + 1, R);
}
// Function to call the queryHelper
// function to find the sum for
// the query
ll query(int L, int R)
{
return queryHelper(root, L, R, 1, 10);
}
// Function to call the UpdateHelper
// function for the point update
void update(int index, int value)
{
UpdateHelper(root, index, 1, 10, value);
}
// Function to perform the operations
// on the tree
void operations()
{
// Creating an empty tree
root = getnode();
// Update the value at position 1 to 10
update(1, 10);
// Update the value at position 3 to 5
update(3, 5);
// Finding sum for the range [2, 8]
cout << query(2, 8) << endl;
// Finding sum for the range [1, 10]
cout << query(1, 10) << endl;
}
// Driver code
int main()
{
operations();
return 0;
}
Java
// Java program for the implementation
// of the Dynamic segment tree and
// perform the range updates on the
// given queries
class GFG {
// Structure of the node
static class Node {
int value;
Node L, R;
}
// Structure to get the newly formed
// node
static Node getnode() {
Node temp = new Node();
temp.value = 0;
temp.L = null;
temp.R = null;
return temp;
}
// Creating the Root node
static Node root = new Node();
// Function to perform the point update
// on the dynamic segment tree
static void UpdateHelper(Node curr, int index, int L, int R, int val) {
// If the index is not overlapping
// with the index
if (L > index || R < index)
return;
// If the index is completely overlapping
// with the index
if (L == R && L == index) {
// Update the value of the node
// to the given value
curr.value = val;
return;
}
// Computing the middle index if none
// of the above base cases are satisfied
int mid = L - (L - R) / 2;
int sum1 = 0, sum2 = 0;
// If the index is in the left subtree
if (index <= mid) {
// Create a new node if the left
// subtree is is null
if (curr.L == null)
curr.L = getnode();
// Recursively call the function
// for the left subtree
UpdateHelper(curr.L, index, L, mid, val);
}
// If the index is in the right subtree
else {
// Create a new node if the right
// subtree is is null
if (curr.R == null)
curr.R = getnode();
// Recursively call the function
// for the right subtree
UpdateHelper(curr.R, index, mid + 1, R, val);
}
// Storing the sum of the left subtree
if (curr.L != null)
sum1 = curr.L.value;
// Storing the sum of the right subtree
if (curr.R != null)
sum2 = curr.R.value;
// Storing the sum of the children into
// the node's value
curr.value = sum1 + sum2;
return;
}
// Function to find the sum of the
// values given by the range
static int queryHelper(Node curr, int a, int b, int L, int R) {
// Return 0 if the root is null
if (curr == null)
return 0;
// If the index is not overlapping
// with the index, then the node
// is not created. So sum is 0
if (L > b || R < a)
return 0;
// If the index is completely overlapping
// with the index, return the node's value
if (L >= a && R <= b)
return curr.value;
int mid = L - (L - R) / 2;
// Return the sum of values stored
// at the node's children
return queryHelper(curr.L, a, b, L, mid) + queryHelper(curr.R, a, b, mid + 1, R);
}
// Function to call the queryHelper
// function to find the sum for
// the query
static int query(int L, int R) {
return queryHelper(root, L, R, 1, 10);
}
// Function to call the UpdateHelper
// function for the point update
static void update(int index, int value) {
UpdateHelper(root, index, 1, 10, value);
}
// Function to perform the operations
// on the tree
static void operations() {
// Creating an empty tree
root = getnode();
// Update the value at position 1 to 10
update(1, 10);
// Update the value at position 3 to 5
update(3, 5);
// Finding sum for the range [2, 8]
System.out.println(query(2, 8));
// Finding sum for the range [1, 10]
System.out.println(query(1, 10));
}
// Driver code
public static void main(String[] args) {
operations();
}
}
// This code is contributed by sanjeev2552
Python3
# C++ program for the implementation # of the Dynamic segment tree and # perform the range updates on the # given queries # Structure of the node class Node: def __init__(self): self.value=-1 self.L, self.R=None,None # Structure to get the newly formed # node def getnode(): temp = Node() temp.value = 0 temp.L = None temp.R = None return temp # Creating the Root node root=None # Function to perform the point update # on the dynamic segment tree def UpdateHelper(curr, index, L, R, val): # If the index is not overlapping # with the index if (L > index or R < index): return # If the index is completely overlapping # with the index if (L == R and L == index) : # Update the value of the node # to the given value curr.value = val return # Computing the middle index if none # of the above base cases are satisfied mid = int(L - (L - R) / 2) sum1 = 0; sum2 = 0 # If the index is in the left subtree if (index <= mid) : # Create a new node if the left # subtree is is None if (curr.L == None): curr.L = getnode() # Recursively call the function # for the left subtree UpdateHelper(curr.L, index, L, mid, val) # If the index is in the right subtree else : # Create a new node if the right # subtree is is None if (curr.R == None): curr.R = getnode() # Recursively call the function # for the right subtree UpdateHelper(curr.R, index, mid + 1, R, val) # Storing the sum of the left subtree if (curr.L): sum1 = curr.L.value # Storing the sum of the right subtree if (curr.R): sum2 = curr.R.value # Storing the sum of the children into # the node's value curr.value = sum1 + sum2 return # Function to find the sum of the # values given by the range def queryHelper(curr, a, b, L, R): # Return 0 if the root is None if (curr == None): return 0 # If the index is not overlapping # with the index, then the node # is not created. So sum is 0 if (L > b or R < a): return 0 # If the index is completely overlapping # with the index, return the node's value if (L >= a and R <= b): return curr.value mid = int(L - (L - R) / 2) # Return the sum of values stored # at the node's children return queryHelper(curr.L, a, b, L, mid) + queryHelper(curr.R, a, b, mid + 1, R) # Function to call the queryHelper # function to find the sum for # the query def query(L, R): return queryHelper(root, L, R, 1, 10) # Function to call the UpdateHelper # function for the point update def update(index, value): UpdateHelper(root, index, 1, 10, value) # Function to perform the operations # on the tree def operations(): global root # Creating an empty tree root = getnode() # Update the value at position 1 to 10 update(1, 10) # Update the value at position 3 to 5 update(3, 5) # Finding sum for the range [2, 8] print(query(2, 8)) # Finding sum for the range [1, 10] print(query(1, 10)) # Driver code if __name__ == '__main__': operations()
C#
using System;
// C# program for the implementation
// of the Dynamic segment tree and
// perform the range updates on the
// given queries
class GFG {
// Structure of the node
public class Node {
public int value;
public Node L, R;
}
// Structure to get the newly formed
// node
static Node getnode() {
Node temp = new Node();
temp.value = 0;
temp.L = null;
temp.R = null;
return temp;
}
// Creating the Root node
static Node root = new Node();
// Function to perform the point update
// on the dynamic segment tree
static void UpdateHelper(Node curr, int index, int L, int R, int val) {
// If the index is not overlapping
// with the index
if (L > index || R < index)
return;
// If the index is completely overlapping
// with the index
if (L == R && L == index) {
// Update the value of the node
// to the given value
curr.value = val;
return;
}
// Computing the middle index if none
// of the above base cases are satisfied
int mid = L - (L - R) / 2;
int sum1 = 0, sum2 = 0;
// If the index is in the left subtree
if (index <= mid) {
// Create a new node if the left
// subtree is is null
if (curr.L == null)
curr.L = getnode();
// Recursively call the function
// for the left subtree
UpdateHelper(curr.L, index, L, mid, val);
}
// If the index is in the right subtree
else {
// Create a new node if the right
// subtree is is null
if (curr.R == null)
curr.R = getnode();
// Recursively call the function
// for the right subtree
UpdateHelper(curr.R, index, mid + 1, R, val);
}
// Storing the sum of the left subtree
if (curr.L != null)
sum1 = curr.L.value;
// Storing the sum of the right subtree
if (curr.R != null)
sum2 = curr.R.value;
// Storing the sum of the children into
// the node's value
curr.value = sum1 + sum2;
return;
}
// Function to find the sum of the
// values given by the range
static int queryHelper(Node curr, int a, int b, int L, int R) {
// Return 0 if the root is null
if (curr == null)
return 0;
// If the index is not overlapping
// with the index, then the node
// is not created. So sum is 0
if (L > b || R < a)
return 0;
// If the index is completely overlapping
// with the index, return the node's value
if (L >= a && R <= b)
return curr.value;
int mid = L - (L - R) / 2;
// Return the sum of values stored
// at the node's children
return queryHelper(curr.L, a, b, L, mid) + queryHelper(curr.R, a, b, mid + 1, R);
}
// Function to call the queryHelper
// function to find the sum for
// the query
static int query(int L, int R) {
return queryHelper(root, L, R, 1, 10);
}
// Function to call the UpdateHelper
// function for the point update
static void update(int index, int value) {
UpdateHelper(root, index, 1, 10, value);
}
// Function to perform the operations
// on the tree
static void operations() {
// Creating an empty tree
root = getnode();
// Update the value at position 1 to 10
update(1, 10);
// Update the value at position 3 to 5
update(3, 5);
// Finding sum for the range [2, 8]
Console.WriteLine(query(2, 8));
// Finding sum for the range [1, 10]
Console.WriteLine(query(1, 10));
}
// Driver code
public static void Main(String[] args) {
operations();
}
}
// This code is contributed by jana_sayantan.
Javascript
<script>
// Javascript program for the implementation
// of the Dynamic segment tree and perform
// the range updates on the given queries
// Structure of the node
class Node
{
constructor()
{
this.L = null;
this.R = null;
this.value = 0;
}
}
// Structure to get the newly formed
// node
function getnode()
{
let temp = new Node();
return temp;
}
// Creating the Root node
let root = new Node();
// Function to perform the point update
// on the dynamic segment tree
function UpdateHelper(curr, index, L, R, val)
{
// If the index is not overlapping
// with the index
if (L > index || R < index)
return;
// If the index is completely overlapping
// with the index
if (L == R && L == index)
{
// Update the value of the node
// to the given value
curr.value = val;
return;
}
// Computing the middle index if none
// of the above base cases are satisfied
let mid = L - parseInt((L - R) / 2, 10);
let sum1 = 0, sum2 = 0;
// If the index is in the left subtree
if (index <= mid)
{
// Create a new node if the left
// subtree is is null
if (curr.L == null)
curr.L = getnode();
// Recursively call the function
// for the left subtree
UpdateHelper(curr.L, index, L, mid, val);
}
// If the index is in the right subtree
else
{
// Create a new node if the right
// subtree is is null
if (curr.R == null)
curr.R = getnode();
// Recursively call the function
// for the right subtree
UpdateHelper(curr.R, index, mid + 1, R, val);
}
// Storing the sum of the left subtree
if (curr.L != null)
sum1 = curr.L.value;
// Storing the sum of the right subtree
if (curr.R != null)
sum2 = curr.R.value;
// Storing the sum of the children into
// the node's value
curr.value = sum1 + sum2;
return;
}
// Function to find the sum of the
// values given by the range
function queryHelper(curr, a, b, L, R)
{
// Return 0 if the root is null
if (curr == null)
return 0;
// If the index is not overlapping
// with the index, then the node
// is not created. So sum is 0
if (L > b || R < a)
return 0;
// If the index is completely overlapping
// with the index, return the node's value
if (L >= a && R <= b)
return curr.value;
let mid = L - parseInt((L - R) / 2, 10);
// Return the sum of values stored
// at the node's children
return queryHelper(curr.L, a, b, L, mid) +
queryHelper(curr.R, a, b, mid + 1, R);
}
// Function to call the queryHelper
// function to find the sum for
// the query
function query(L, R)
{
return queryHelper(root, L, R, 1, 10);
}
// Function to call the UpdateHelper
// function for the point update
function update(index, value)
{
UpdateHelper(root, index, 1, 10, value);
}
// Function to perform the operations
// on the tree
function operations()
{
// Creating an empty tree
root = getnode();
// Update the value at position 1 to 10
update(1, 10);
// Update the value at position 3 to 5
update(3, 5);
// Finding sum for the range [2, 8]
document.write(query(2, 8) + "</br>");
// Finding sum for the range [1, 10]
document.write(query(1, 10) + "</br>");
}
// Driver code
operations();
// This code is contributed by mukesh07
</script>
Producción:
5 15
Complejidad temporal: O(Q * logN)
Espacio auxiliar: O(N)
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por akashsharma01 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA