Kth La suma más pequeña de subarreglos continuos de números positivos

Dada una array ordenada de números positivos, nuestra tarea es encontrar la k-ésima suma más pequeña del subarreglo continuo.

Ejemplos:

Entrada: a[] = {1, 2, 3, 4, 5, 6}
k = 4
Salida: 3
Explicación: Lista de suma de subarreglo ordenada: {1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 9, 9, 10, 11, 12, 14, 15, 15, 18, 20, 21}. El cuarto elemento más pequeño es 3.

Entrada: a[] = {1, 2, 3, 4, 5, 6}
k = 13
Salida: 10

Un enfoque ingenuo es generar primero todas las sumas de subarreglos continuos que se pueden hacer en O (N ^ 2) precalculando la suma de prefijos. Ordene la array de suma y dé el k-ésimo elemento más pequeño.

Un mejor enfoque (para arreglos con una suma pequeña) es usar la búsqueda binaria. Primero calcularemos previamente una array de suma de prefijos. Ahora aplicamos la búsqueda binaria en el número que son posibles candidatos para la k-ésima suma más pequeña que estará en el rango [0, suma total de la array]. Por ahora, supongamos que tenemos una función llamada calcularRango que nos dará el rango de cualquier número en la array ordenada de la suma continua de subarreglos. En la búsqueda binaria, usaremos esta función de calcular rango para verificar si el rango del elemento medio es menor que K, si es así, reducimos el punto de inicio a medio + 1; de lo contrario, si es mayor o igual a K, luego reducimos el final apuntar a mid-1 y también actualizar la variable de respuesta.
Ahora volvamos a la función de cálculo de rango. Aquí, también usaremos la búsqueda binaria pero en nuestra array de suma de prefijos. Repetiremos en nuestra array y supongamos que estamos en el i-ésimo índice, contaremos cuántos subarreglo se pueden hacer con el elemento inicial como este i-ésimo elemento cuya suma es menor que el elemento medio cuyo rango tenemos que calcular. Lo hacemos para todos los elementos y agregamos el recuento de cada uno de los cuales tenemos el rango del elemento medio. Para contar el número del subarreglo que comienza con el i-ésimo índice, usamos aplicar binario en la suma del prefijo.

Implementación de C++ para aclarar las cosas.

// CPP program to find k-th smallest sum
#include "algorithm"
#include "iostream"
#include "vector"
using namespace std;
  
int CalculateRank(vector<int> prefix, int n, int x)
{
    int cnt;
  
    // Initially rank is 0.
    int rank = 0;
    int sumBeforeIthindex = 0;
    for (int i = 0; i < n; ++i) {
  
        // Calculating the count the subarray with
        // starting at ith index
        cnt = upper_bound(prefix.begin(), prefix.end(), 
                sumBeforeIthindex + x) - prefix.begin();
  
        // Subtracting the subarrays before ith index.
        cnt -= i;
  
        // Adding the count to rank.
        rank += cnt;
        sumBeforeIthindex = prefix[i];
    }
    return rank;
}
  
int findKthSmallestSum(int a[], int n, int k)
{
    // PrefixSum array.
    vector<int> prefix;
  
    // Total Sum initially 0.
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
        prefix.push_back(sum);
    }
  
    // Binary search on possible
    // range i.e [0, total sum]
    int ans = 0;
    int start = 0, end = sum;
    while (start <= end) {
  
        int mid = (start + end) >> 1;
  
        // Calculating rank of the mid and 
        // comparing with K
        if (CalculateRank(prefix, n, mid) >= k) {
             
            // If greater or equal store the answer
            ans = mid;
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
  
    return ans;
}
  
int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6 };
    int k = 13;
    int n = sizeof(a)/sizeof(a[0]);
    cout << findKthSmallestSum(a, n, k);
    return 0;
}

10

Complejidad temporal: O(N Log N Log SUM). Aquí N es el número de elementos y SUM es la suma de la array.

La función CalculateRank toma el tiempo O (N log N) y se llama Log SUM times.