Count increasing subsequence length k

def solution(nums, k):

    """
    1)

    sol_startFrom(i | cur_len)
    -> sol_startFrom(next_i | cur_len - 1) for all possible next_i

    2)  i: 0 -> len(nums) - 1
        next_i | i: i + 1 -> len(nums) - 1
        cur_len: k -> 1

    """

    sol_startFrom = [
        [None for __ in range(len(nums))]
        for _ in range(k)
    ]
    solve_correct(sol_startFrom, nums = nums, k = k)
    final_ans = sum(
        sol_startFrom[k - 1][dp_i]
        for dp_i in range(0, len(sol_startFrom[0]))
    )
    return final_ans
def solve_correct(sol_startFrom, *, nums, k):
    for cur_len in range(1, k + 1, 1):
        for i in range(len(nums) - 1, -1, -1):
            dp_i = i; dp_cur_len = cur_len - 1

            ans = sol_startFrom[dp_cur_len][dp_i]
            if ans is not None:
                continue

            if i == len(nums) - 1:
                ans = 1 if (cur_len == 1) else 0
            elif cur_len == 1:
                ans = 1

            else:
                ans = 0
                for next_i in range(i + 1, len(nums)):
                    dp_next_i = next_i

                    if not (nums[next_i] > nums[i]):
                        continue

                    ans += sol_startFrom[dp_cur_len - 1][dp_next_i]

            sol_startFrom[dp_cur_len][dp_i] = ans
    return

class SegmentTree:
    def __init__(self, func, default, arr=None):
        """
        Initialize the Segment Tree.
        :time complexity: O(n), where n is the number of elements in `arr` (if provided).
        """
        self.func = func
        self.default = default
        self.n = 1
        while self.n < (len(arr) if arr else 0):
            self.n <<= 1  # Find the next power of two
        self.size = 2 * self.n
        self.tree = [self.default] * self.size
        self.lazy = [0] * self.size  # Lazy propagation array

        if arr:
            for i, value in enumerate(arr):
                self.tree[self.n + i] = value
            for i in range(self.n - 1, 0, -1):
                self.tree[i] = self.func(
                    self.tree[2 * i], self.tree[2 * i + 1]
                )

    def update_range(self, l, r, val):
        """
        Add 'val' to all elements in the range [l, r).
        time complexity: O(log n), where n is the number of elements.
        """
        def _push(self):
            """
            Push the lazy updates to the children nodes.
            :time complexity: O(1)
            """
            if self.lazy[node] != 0:
                self.tree[node] += self.lazy[node] * (node_right - node_left + 1)  # Update current node
                if node < self.n:  # If not a leaf node
                    self.lazy[2 * node] += self.lazy[node]
                    self.lazy[2 * node + 1] += self.lazy[node]
                self.lazy[node] = 0

        def _update(node, node_left, node_right):
            self._push(node, node_left, node_right)
            if node_right <= l or r <= node_left:
                return
            if l <= node_left and node_right <= r:
                self.lazy[node] += val
                self._push(node, node_left, node_right)
                return
            mid = (node_left + node_right) // 2
            _update(2 * node, node_left, mid)
            _update(2 * node + 1, mid, node_right)
            self.tree[node] = self.func(self.tree[2 * node], self.tree[2 * node + 1])

        _update(1, 0, self.n)

    def update_point(self, idx, value):
        """
        Update the value at a specific index and propagate the change.

        :param idx: 0-based index to update.
        :param value: New value.
        :time complexity: O(log n), where n is the number of elements.
        """
        if idx < 0 or idx >= self.n:
            raise IndexError("Index out of bounds")
        node = self.n + idx
        self.tree[node] = value
        while node > 1:
            node //= 2
            self.tree[node] = self.func(self.tree[2 * node], self.tree[2 * node + 1])

    def query_range(self, l, r):
        """
        Query the aggregated value in the range [l, r).

        :param l: Left index (inclusive, 0-based).
        :param r: Right index (exclusive, 0-based).
        :return: Aggregated result.
        :time complexity: O(log n), where n is the number of elements.
        """
        if l < 0 or r > self.n or l > r:
            raise IndexError("Invalid query range")
        res = self.default
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                res = self.func(res, self.tree[l] + self.lazy[l])
                l += 1
            if r % 2:
                r -= 1
                res = self.func(res, self.tree[r] + self.lazy[r])
            l //= 2
            r //= 2
        return res


def count_increasing_subsequence(nums, k):
    sol_startFrom = [
        [None for __ in range(len(nums))]
        for _ in range(k)
    ]
    solve(sol_startFrom, nums = nums, k = k)
    final_ans = sum(
        sol_startFrom[k - 1][dp_i]
        for dp_i in range(0, len(sol_startFrom[0]))
    )
    return final_ans
def solve(sol_startFrom, *, nums, k):
    for cur_len in range(1, k + 1, 1):
        for i in range(len(nums) - 1, -1, -1):
            dp_i = i; dp_cur_len = cur_len - 1

            ans = sol_startFrom[dp_cur_len][dp_i]
            if ans is not None:
                continue

            if i == len(nums) - 1:
                ans = 1 if (cur_len == 1) else 0
            elif cur_len == 1:
                ans = 1

            else:
                ans = 0
                for next_i in range(i + 1, len(nums)):
                    dp_next_i = next_i

                    if not (nums[next_i] > nums[i]):
                        continue

                    ans += sol_startFrom[dp_cur_len - 1][dp_next_i]

            sol_startFrom[dp_cur_len][dp_i] = ans
    return

print(count_increasing_subsequence([2, 6, 4, 5, 7], 3)) # 5
print(count_increasing_subsequence([12, 8, 11, 13, 10, 15, 14, 16, 20], 4)) # 39