Good Subsequence Queries - Solution & Explanation

Problem Overview: You are given an array and multiple queries. Each query asks about the number of good subsequences that satisfy a specific constraint defined in the problem. The challenge is answering many queries efficiently without recomputing subsequences from scratch every time.

Approach 1: Brute Force Enumeration (O(2^n) time, O(n) space)

The most direct idea is to generate every possible subsequence of the array and check whether it satisfies the “good” condition. For each query, filter subsequences that fall within the required constraints and count them. This approach uses recursive generation or bitmask enumeration. The problem is exponential growth: an array of size n has 2^n subsequences, so even moderate inputs become impossible to handle.

Approach 2: Dynamic Programming per Query (O(n^2) time, O(n) space)

A better strategy uses dynamic programming to build subsequences incrementally. Let dp[i] represent the number of valid subsequences ending at index i. For each position, iterate over previous indices and extend subsequences that still satisfy the “good” constraint. For every query, recompute or partially recompute these values within the relevant range. This reduces exponential complexity but still becomes slow when both n and the number of queries are large.

Approach 3: DP with Fenwick Tree / Segment Tree (O((n + q) log n) time, O(n) space)

The optimal solution combines dynamic programming with a range data structure such as a segment tree or Fenwick tree. Instead of scanning all previous elements, the structure maintains aggregated counts of valid subsequences. After coordinate compression (if values are large), each step performs fast prefix or range queries to compute how many subsequences can extend to the current element. Updates insert the new counts back into the tree. Queries can then be answered in logarithmic time using the maintained prefix sums or range aggregates.

This method avoids recomputing subsequences repeatedly. Each element contributes once, and each query performs only logarithmic operations. The combination of DP state transitions and tree-based range queries is a common technique for subsequence counting problems where constraints depend on relative ordering or value ranges.

Recommended for interviews: Interviewers expect the optimized DP with a Fenwick tree or segment tree. Showing the brute-force idea demonstrates understanding of subsequence generation, but recognizing that repeated scans are too slow and replacing them with logarithmic range queries shows strong algorithmic skill.