Given an array arr[] of length N, the task is to find the number of strictly increasing sub-sequences in the given array.
Examples:
Input: arr[] = {1, 2, 3}
Output: 7
All increasing sub-sequences will be:
1) {1}
2) {2}
3) {3}
4) {1, 2}
5) {1, 3}
6) {2, 3}
7) {1, 2, 3}
Thus, answer = 7
Input: arr[] = {3, 2, 1}
Output: 3
Approach: An O(N2) approach has already been discussed in this article. Here, an approach with O(NlogN) time using segment tree data structure will be discussed.
In the previous article, the recurrence relation used was:
dp[i] = 1 + summation(dp[j]), where i <jarr[i]
Due to the fact that the entire sub-array arr[i+1…n-1] was being iterated for each state, an extra O(N) time was being used to solve it. Thus, the complexity was (N2).
The idea is to avoid iterating the O(N) extra loop for each state and reducing its complexity to Log(N).
Assumption: The number of strictly increasing sub-sequences starting from each index ‘i’, where i is greater than a number ‘k’ is known.
Using this above assumption, the number of increasing sub-sequences starting from index ‘k’ can be found in log(N) time.
Therefore, the summation for all the indexes ‘i’ greater than ‘k’ must be found. But the catch is arr[i] must be greater than arr[k]. To deal with the problem, the following can be done:
1. For each element of the array, its index is found in the array was sorted. Example – {7, 8, 1, 9, 4} Here, ranks will be:
7 -> 3
8 -> 4
1 -> 1
9 -> 5
4 -> 2
2. A segment tree of length ‘N’ is created to answer a range-sum query.
3. To answer the query while solving for index ‘k’, the rank of arr[k] is found first. Let’s say the rank is R. Then, in the segment tree, the range-sum from index {R to N-1} is found.
4. Then, the segment-tree is point updated as segment-(R-1) equals 1 + segtree-query(R, N-1) + segtree-query(R-1, R-1)
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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> |
Output:
11
Related Topic: Segment Tree
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
