Binary Indexed Tree – Página 2

Encontrar el número de triángulos entre segmentos de línea horizontal y vertical

julio 5, 2022 Rudeus Greyrat

Requisitos previos: BIT Dados ‘n’ segmentos de línea, cada uno de ellos es horizontal o vertical, encuentre el número máximo de triángulos (incluidos los triángulos con área cero) que se pueden formar uniendo los puntos de intersección de los segmentos de línea. No se superponen dos segmentos de línea horizontal, ni tampoco dos segmentos de … Continue reading «Encontrar el número de triángulos entre segmentos de línea horizontal y vertical»

Cuente los elementos más pequeños en el lado derecho y los elementos más grandes en el lado izquierdo usando el árbol de índice binario

julio 5, 2022 Rudeus Greyrat

Dada una array arr[] de tamaño N . La tarea es encontrar elementos más pequeños en el lado derecho y elementos más grandes en el lado izquierdo para cada elemento arr[i] en la array dada. Ejemplos: Entrada: arr[] = {12, 1, 2, 3, 0, 11, 4} Salida: Menor derecha: 6 1 1 1 0 1 … Continue reading «Cuente los elementos más pequeños en el lado derecho y los elementos más grandes en el lado izquierdo usando el árbol de índice binario»

proto de Emde Boas Árboles | Conjunto 1 (Antecedentes e Introducción)

julio 5, 2022 Rudeus Greyrat

Consideremos el siguiente enunciado del problema y pensemos en diferentes soluciones para él. Dado un conjunto S de elementos tales que los elementos se toman del universo {0, 1, …. u-1}, realice las siguientes operaciones de manera eficiente. insert(x) : Agrega un elemento x al conjunto+ S. isEmpty() : Devuelve verdadero si S está vacío, … Continue reading «proto de Emde Boas Árboles | Conjunto 1 (Antecedentes e Introducción)»

Suma de intervalo y actualización con número de divisores

julio 5, 2022 Rudeus Greyrat

Dada una array A de N enteros. Debe responder dos tipos de consultas: 1. Actualizar [l, r]: para cada i en el rango de l a r, actualice A i con D (A i ), donde D (A i ) representa el número de divisores de A i 2. Consulta [l, r]: calcule la suma … Continue reading «Suma de intervalo y actualización con número de divisores»

¿Cómo prepararse para ACM – ICPC?

julio 5, 2022 Rudeus Greyrat

ACM ICPC ( A ssociation for Computing M achinery – I nternational Collegiate P rogramming C ontest ) es un concurso mundial anual de programación de varios niveles que se organiza desde hace más de trece años. El concurso está patrocinado por IBM. Este artículo se enfoca en todos los temas que son importantes … Continue reading «¿Cómo prepararse para ACM – ICPC?»

Contar inversiones de tamaño k en una array dada

julio 5, 2022 Rudeus Greyrat

Dada una array de n enteros distintos y un entero k. Averigüe el número de subsecuencias de tal que , y . En otras palabras, genera el número total de inversiones de longitud k. Ejemplos: Input : a[] = {9, 3, 6, 2, 1}, k = 3 Output : 7 The seven inversions are {9, … Continue reading «Contar inversiones de tamaño k en una array dada»

Los 10 mejores algoritmos y estructuras de datos para la programación competitiva

julio 5, 2022 Rudeus Greyrat

En esta publicación, discutiremos los 10 algoritmos y estructuras de datos más importantes para la codificación competitiva. Temas: Algoritmos gráficos Programación dinámica Buscando y Ordenando: Teoría de Números y Otras Matemáticas Algoritmos de flujo geométrico y de red Estructuras de datos Los enlaces a continuación cubren los algoritmos más importantes y los temas de … Continue reading «Los 10 mejores algoritmos y estructuras de datos para la programación competitiva»

Subsecuencia creciente de suma máxima utilizando árbol indexado binario

julio 5, 2022 Rudeus Greyrat

Dada una array de tamaño n. Encuentra la suma máxima de una subsecuencia creciente. Ejemplos: Input : arr[] = { 1, 20, 4, 2, 5 } Output : Maximum sum of increasing subsequence is = 21 The subsequence 1, 20 gives maximum sum which is 21 Input : arr[] = { 4, 2, 3, 1, … Continue reading «Subsecuencia creciente de suma máxima utilizando árbol indexado binario»

Número de elementos mayores que K en el rango L a R utilizando Fenwick Tree (consultas sin conexión)

julio 5, 2022 Rudeus Greyrat

Prerrequisitos: Fenwick Tree (Árbol indexado binario) Dada una array de N números y una cantidad de consultas donde cada consulta contendrá tres números (l, r y k). La tarea es calcular el número de elementos del arreglo que son mayores que K en el subarreglo [L, R]. Ejemplos: Input: n=6 q=2 arr[ ] = { 7, … Continue reading «Número de elementos mayores que K en el rango L a R utilizando Fenwick Tree (consultas sin conexión)»

XOR de elementos en un rango dado con actualizaciones usando Fenwick Tree

julio 5, 2022 Rudeus Greyrat

Dada una array A[] de enteros y una array Q que consta de consultas de los siguientes dos tipos: (1, L, R) : Devuelve XOR de todos los elementos presentes entre los índices L y R . (2, I, val) : actualice A[I] a A[I] XOR val . La tarea es resolver cada consulta e … Continue reading «XOR de elementos en un rango dado con actualizaciones usando Fenwick Tree»