-Consider for index ith -Now at each index we want to find number of subsequences ending at index i of length 1 , 2 , 3 ... k+1 ; How we can compute this ? say arr[i] == 5 if know number of subsequences which end at value either 1 or 2 or 3 or 4 from index 1 to index i+1 pls read above lines again if not clear. so now wat the equation becomes no of subsequences of length k+1 which end at index i= number of subsequences of length k which end at [value 1] from index range 1 to (i-1) of given array + number of subsequences of length k which end at [value 2] from index range 1 to (i-1) of given array + number of subsequences of length k which end at [value 3] from index range 1 to (i-1) of given array + number of subsequences of length k which end at [value 4] from index range 1 to (i-1) of given array For this part we can use Segemnt Tree to compute sum of subsequences ... Segment tree : we use tree[1] to store number of subsequences which end at value 1 : we use tree[2] to store number of subsequences which end at value 2 But we want number of subsequences of length 1 , 2 ,3 .. (k+1) So we will use 2-d Segment Tree