Длина самой длинной возрастающей подпоследовательности (LIS) с использованием дерева сегментов

Учитывая массив arr[] размера N , задача состоит в том, чтобы подсчитать количество самых длинных возрастающих подпоследовательностей, присутствующих в данном массиве.

Пример:

Input: arr[] = {2, 2, 2, 2, 2}
Output: 5
Explanation: The length of the longest increasing subsequence is 1, i.e. {2}. Therefore, count of longest increasing subsequences of length 1 is 5. 
 

Input: arr[] = {1, 3, 5, 4, 7}
Output: 2
Explanation: The length of the longest increasing subsequence is 4, and there are 2 longest increasing subsequences of length 4, i.e. {1, 3, 4, 7} and {1, 3, 5, 7}.

Подход: В этой статье уже обсуждался подход к данной проблеме с использованием динамического программирования.
В этой статье предлагается другой подход с использованием деревьев сегментов. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте дерево сегментов как массив пар, первоначально содержащий пары (0, 0), где 1 ^-й элемент представляет длину LIS, а 2- ^й элемент элемент представляет количество LIS текущей длины.
• Аналогично подходу, обсуждаемому в этой статье, можно вычислить 1 ^-й элемент дерева отрезков.
• 2- ^й элемент дерева сегментов можно рассчитать, выполнив следующие шаги:
  • В случаях, когда длина левого дочернего элемента > длины правого дочернего элемента , родительский узел становится равным левому дочернему элементу, так как LIS будет левым дочерним элементом.
  • В случаях, когда длина левого дочернего элемента < длины правого дочернего элемента , родительский узел становится равным правому дочернему элементу, поскольку LIS будет правым дочерним элементом.
  • В случаях, когда длина левого дочернего элемента = длина правого дочернего узла, родительский узел становится равным сумме количества LIS левого дочернего элемента и правого дочернего элемента.
• Требуемый ответ — 2- ^й элемент корня дерева отрезков.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)

Связанная тема: Дерево сегментов