Cuente el número de subsecuencias crecientes: O (NlogN)

Dada una array arr[] de longitud N , la tarea es encontrar el número de subsecuencias estrictamente crecientes en la array dada.

Ejemplos:  

Entrada: arr[] = {1, 2, 3} 
Salida: 7 
Todas las subsecuencias crecientes serán: 
1) {1} 
2) {2} 
3) {3} 
4) {1, 2} 
5) {1 , 3} 
6) {2, 3} 
7) {1, 2, 3} 
Por lo tanto, respuesta = 7
Entrada: arr[] = {3, 2, 1} 
Salida: 3  

Enfoque: Un enfoque O(N ² ) ya ha sido discutido en este artículo. Aquí, se discutirá un enfoque con el tiempo O (NlogN) utilizando la estructura de datos del árbol de segmentos.
En el artículo anterior, la relación de recurrencia utilizada fue:  

dp[i] = 1 + sumatoria(dp[j]), donde i <jarr[i] 
 

Debido al hecho de que todo el subconjunto arr[i+1…n-1] se iteraba para cada estado, se usaba un tiempo O(N) adicional para resolverlo. Así, la complejidad era (N ² ).
La idea es evitar iterar el bucle adicional O(N) para cada estado y reducir su complejidad a Log(N).
Suposición: Se conoce el número de subsecuencias estrictamente crecientes a partir de cada índice ‘i’, donde i es mayor que un número ‘k’. 
Usando esta suposición anterior, el número de subsecuencias crecientes a partir del índice ‘k’ se puede encontrar en tiempo log(N).
Por lo tanto, se debe encontrar la suma de todos los índices ‘i’ mayores que ‘k’. Pero la captura es arr[i] debe ser mayor que arr[k]. Para tratar el problema, se puede hacer lo siguiente:  

1. Para cada elemento de la array, su índice se encuentra en la array ordenada. Ejemplo: {7, 8, 1, 9, 4} Aquí, los rangos serán: 

7 -> 3 
8 -> 4 
1 -> 1 
9 -> 5 
4 -> 2 
 

2. Se crea un árbol de segmentos de longitud ‘N’ para responder a una consulta de suma de rango.

3. Para responder a la consulta mientras se resuelve el índice ‘k’, primero se encuentra el rango de arr[k] . Digamos que el rango es R . Luego, en el árbol de segmentos, se encuentra la suma de rango del índice {R a N-1} .

4. Luego, el árbol de segmento se actualiza como segmento-(R-1) igual a 1 + consulta de árbol de segmento (R, N-1) + consulta de árbol de segmento (R-1, R-1)

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
#define N 10000
  
// Segment tree array
int seg[3 * N];
  
// Function for point update in segment tree
int update(int in, int l, int r, int up_in, int val)
{
    // Base case
    if (r < up_in || l > up_in)
        return seg[in];
  
    // If l==r==up
    if (l == up_in and r == up_in)
        return seg[in] = val;
  
    // Mid element
    int m = (l + r) / 2;
  
    // Updating the segment tree
    return seg[in] = update(2 * in + 1, l, m, up_in, val)
                     + update(2 * in + 2, m + 1, r, up_in, val);
}
  
// Function for the range sum-query
int query(int in, int l, int r, int l1, int r1)
{
    // Base case
    if (l > r)
        return 0;
    if (r < l1 || l > r1)
        return 0;
    if (l1 <= l and r <= r1)
        return seg[in];
  
    // Mid element
    int m = (l + r) / 2;
  
    // Calling for the left and the right subtree
    return query(2 * in + 1, l, m, l1, r1)
           + query(2 * in + 2, m + 1, r, l1, r1);
}
  
// Function to return the count
int findCnt(int* arr, int n)
{
    // Copying array arr to sort it
    int brr[n];
    for (int i = 0; i < n; i++)
        brr[i] = arr[i];
  
    // Sorting array brr
    sort(brr, brr + n);
  
    // Map to store the rank of each element
    map<int, int> r;
    for (int i = 0; i < n; i++)
        r[brr[i]] = i + 1;
  
    // dp array
    int dp[n] = { 0 };
  
    // To store the final answer
    int ans = 0;
  
    // Updating the dp array
    for (int i = n - 1; i >= 0; i--) {
  
        // Rank of the element
        int rank = r[arr[i]];
  
        // Solving the dp-states using segment tree
        dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
  
        // Updating the final answer
        ans += dp[i];
  
        // Updating the segment tree
        update(0, 0, n - 1, rank - 1,
               dp[i] + query(0, 0, n - 1, rank - 1, rank - 1));
    }
  
    // Returning the final answer
    return ans;
}
  
// Driver code
int main()
{
    int arr[] = { 1, 2, 10, 9 };
    int n = sizeof(arr) / sizeof(int);
  
    cout << findCnt(arr, n);
  
    return 0;
}

// Java implementation of the approach
import java.util.*;
  
class GFG
{
  
    static final int N = 10000;
  
    // Segment tree array
    static int[] seg = new int[3 * N];
  
    // Function for point update in segment tree
    static int update(int in, int l, int r, int up_in, int val)
    {
        // Base case
        if (r < up_in || l > up_in)
            return seg[in];
  
        // If l==r==up
        if (l == up_in && r == up_in)
            return seg[in] = val;
  
        // Mid element
        int m = (l + r) / 2;
  
        // Updating the segment tree
        return seg[in] = update(2 * in + 1, l, m, up_in, val) +
                update(2 * in + 2, m + 1, r, up_in, val);
    }
  
    // Function for the range sum-query
    static int query(int in, int l, int r, int l1, int r1) 
    {
        // Base case
        if (l > r)
            return 0;
        if (r < l1 || l > r1)
            return 0;
        if (l1 <= l && r <= r1)
            return seg[in];
  
        // Mid element
        int m = (l + r) / 2;
  
        // Calling for the left and the right subtree
        return query(2 * in + 1, l, m, l1, r1) +
                query(2 * in + 2, m + 1, r, l1, r1);
    }
  
    // Function to return the count
    static int findCnt(int[] arr, int n) 
    {
        // Copying array arr to sort it
        int[] brr = new int[n];
        for (int i = 0; i < n; i++)
            brr[i] = arr[i];
  
        // Sorting array brr
        Arrays.sort(brr);
  
        // Map to store the rank of each element
        HashMap<Integer, Integer> r = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++)
            r.put(brr[i], i + 1);
  
        // dp array
        int dp[] = new int[n];
  
        // To store the final answer
        int ans = 0;
  
        // Updating the dp array
        for (int i = n - 1; i >= 0; i--)
        {
  
            // Rank of the element
            int rank = r.get(arr[i]);
  
            // Solving the dp-states using segment tree
            dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
  
            // Updating the final answer
            ans += dp[i];
  
            // Updating the segment tree
            update(0, 0, n - 1, rank - 1, dp[i] +
                    query(0, 0, n - 1, rank - 1, rank - 1));
        }
  
        // Returning the final answer
        return ans;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 10, 9 };
        int n = arr.length;
  
        System.out.print(findCnt(arr, n));
  
    }
}
  
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
  
N = 10000
  
# Segment tree array
seg = [0] * (3 * N)
  
# Function for point update in segment tree
def update(In, l, r, up_In, val):
      
    # Base case
    if (r < up_In or l > up_In):
        return seg[In]
  
    # If l==r==up
    if (l == up_In and r == up_In):
        seg[In] = val
        return val
  
    # Mid element
    m = (l + r) // 2
  
    # Updating the segment tree
    seg[In] = update(2 * In + 1, l, m, up_In, val) + update(2 * In + 2, m + 1, r, up_In, val)
    return seg[In]
  
  
# Function for the range sum-query
def query(In, l, r, l1, r1):
  
    # Base case
    if (l > r):
        return 0
    if (r < l1 or l > r1):
        return 0
    if (l1 <= l and r <= r1):
        return seg[In]
  
    # Mid element
    m = (l + r) // 2
  
    # CallIng for the left and the right subtree
    return query(2 * In + 1, l, m, l1, r1)+ query(2 * In + 2, m + 1, r, l1, r1)
  
  
# Function to return the count
def fIndCnt(arr, n):
  
    # Copying array arr to sort it
    brr = [0] * n
    for i in range(n):
        brr[i] = arr[i]
  
    # Sorting array brr
    brr = sorted(brr)
  
    # Map to store the rank of each element
    r = dict()
    for i in range(n):
        r[brr[i]] = i + 1
  
    # dp array
    dp = [0] * n
  
    # To store the final answer
    ans = 0
  
    # Updating the dp array
    for i in range(n - 1, -1, -1):
  
        # Rank of the element
        rank = r[arr[i]]
  
        # Solving the dp-states using segment tree
        dp[i] = 1 + query(0, 0, n - 1, rank, n - 1)
  
        # UpdatIng the final answer
        ans += dp[i]
  
        # Updating the segment tree
        update(0, 0, n - 1, rank - 1,dp[i] + query(0, 0, n - 1, rank - 1, rank - 1))
  
    # Returning the final answer
    return ans
  
# Driver code
  
arr = [1, 2, 10, 9]
n = len(arr)
  
print(fIndCnt(arr, n))
  
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
using System.Collections.Generic;
  
class GFG
{
  
    static readonly int N = 10000;
  
    // Segment tree array
    static int[] seg = new int[3 * N];
  
    // Function for point update In segment tree
    static int update(int In, int l, int r, 
                        int up_in, int val)
    {
        // Base case
        if (r < up_in || l > up_in)
            return seg[In];
  
        // If l==r==up
        if (l == up_in && r == up_in)
            return seg[In] = val;
  
        // Mid element
        int m = (l + r) / 2;
  
        // Updating the segment tree
        return seg[In] = update(2 * In + 1, l, m, up_in, val) +
                update(2 * In + 2, m + 1, r, up_in, val);
    }
  
    // Function for the range sum-query
    static int query(int In, int l, int r, int l1, int r1) 
    {
        // Base case
        if (l > r)
            return 0;
        if (r < l1 || l > r1)
            return 0;
        if (l1 <= l && r <= r1)
            return seg[In];
  
        // Mid element
        int m = (l + r) / 2;
  
        // Calling for the left and the right subtree
        return query(2 * In + 1, l, m, l1, r1) +
                query(2 * In + 2, m + 1, r, l1, r1);
    }
  
    // Function to return the count
    static int findCnt(int[] arr, int n) 
    {
        // Copying array arr to sort it
        int[] brr = new int[n];
        for (int i = 0; i < n; i++)
            brr[i] = arr[i];
  
        // Sorting array brr
        Array.Sort(brr);
  
        // Map to store the rank of each element
        Dictionary<int, int> r = new Dictionary<int, int>();
        for (int i = 0; i < n; i++)
            r.Add(brr[i], i + 1);
  
        // dp array
        int []dp = new int[n];
  
        // To store the readonly answer
        int ans = 0;
  
        // Updating the dp array
        for (int i = n - 1; i >= 0; i--)
        {
  
            // Rank of the element
            int rank = r[arr[i]];
  
            // Solving the dp-states using segment tree
            dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
  
            // Updating the readonly answer
            ans += dp[i];
  
            // Updating the segment tree
            update(0, 0, n - 1, rank - 1, dp[i] +
                    query(0, 0, n - 1, rank - 1, rank - 1));
        }
  
        // Returning the readonly answer
        return ans;
    }
  
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = { 1, 2, 10, 9 };
        int n = arr.Length;
  
        Console.Write(findCnt(arr, n));
  
    }
}
  
// This code is contributed by PrinciRaj1992

<script>
  
// Javascript implementation of the approach
  
var N = 10000;
  
// Segment tree array
var seg = Array(3*N).fill(0);
  
// Function for point update inVal segment tree
function update(inVal, l, r, up_in, val)
{
    // Base case
    if (r < up_in || l > up_in)
        return seg[inVal];
  
    // If l==r==up
    if (l == up_in && r == up_in)
        return seg[inVal] = val;
  
    // Mid element
    var m = parseInt((l + r) / 2);
  
    // Updating the segment tree
    seg[inVal] = update(2 * inVal + 1, l, m, up_in, val)
                     + update(2 * inVal + 2, m + 1, r, up_in, val);
    return seg[inVal];
}
  
// Function for the range sum-query
function query(inVal, l, r, l1, r1)
{
    // Base case
    if (l > r)
        return 0;
    if (r < l1 || l > r1)
        return 0;
    if (l1 <= l && r <= r1)
        return seg[inVal];
  
    // Mid element
    var m = parseInt((l + r) / 2);
  
    // Calling for the left and the right subtree
    return query(2 * inVal + 1, l, m, l1, r1)
           + query(2 * inVal + 2, m + 1, r, l1, r1);
}
  
// Function to return the count
function findCnt(arr, n)
{
    // Copying array arr to sort it
    var brr = Array(n);
    for (var i = 0; i < n; i++)
        brr[i] = arr[i];
  
    // Sorting array brr
    brr.sort((a, b)=> a-b);
  
    // Map to store the rank of each element
    var r = new Map();
    for (var i = 0; i < n; i++)
        r[brr[i]] = i + 1;
  
    // dp array
    var dp = Array(n).fill(0);
  
    // To store the final answer
    var ans = 0;
  
    // Updating the dp array
    for (var i = n - 1; i >= 0; i--) {
  
        // Rank of the element
        var rank = r[arr[i]];
  
        // Solving the dp-states using segment tree
        dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
  
        // Updating the final answer
        ans += dp[i];
  
        // Updating the segment tree
        update(0, 0, n - 1, rank - 1,
               dp[i] + query(0, 0, n - 1, rank - 1, rank - 1));
    }
  
    // Returning the final answer
    return ans;
}
  
// Driver code
var arr = [1, 2, 10, 9 ];
var n = arr.length;
document.write( findCnt(arr, n));
  
</script>

11

Tema relacionado: Árbol de segmentos