[FEATURE REQUEST] Add Wavelet Tree Data Structure

[space0032]

What would you like to Propose?

What would you like to propose?

I would like to propose adding the Wavelet Tree data structure to the repository.

A Wavelet Tree is a succinct data structure used to represent sequences (like arrays or strings) in compressed space while supporting complex range queries in logarithmic time. It is a fundamental data structure in competitive programming, bioinformatics, and text compression.

Issue details

Proposed Implementation:
I plan to implement the Wavelet Tree to support the following operations efficiently:

1. rank(x, i): Counts the number of occurrences of element x in the prefix of the array up to index i.
2. kthSmallest(l, r, k): Finds the k-th smallest element in the subarray from index l to r without needing to sort the subarray.

Implementation specifics:

• Folder: src/main/java/com/thealgorithms/datastructures/trees/
• Filename: WaveletTree.java
• Time Complexity: $O(\log U)$ per query, where $U$ is the range of values (alphabet size).
• Space Complexity: $O(N \log U)$ to store the bit vectors.

Additional Information

This data structure is currently missing from the repository and would be a great advanced addition to the trees package. It provides an elegant alternative to 2D Segment Trees or Merge Sort Trees for answering range quantile queries.

I would like to be assigned to this issue so I can work on the implementation, provide well-documented code, and include a full suite of JUnit tests. Let me know if this looks good!

Issue details

Problem Description:
The repository currently lacks an efficient data structure for querying exact element counts in a prefix (Rank) and finding the k-th smallest element in a specific subarray (Quantile/Range queries) without modifying or sorting the array.

Proposed Solution:
Introduce a WaveletTree.java class. The Wavelet Tree solves these problems by recursively partitioning the value range (alphabet) and storing the decisions in bit vectors.

Expected Deliverables:

1. A WaveletTree class with a constructor that builds the tree in $O(N \log U)$ time.
2. Implementation of the rank(element, index) method.
3. Implementation of the kthSmallest(left, right, k) method.
4. Clean, well-commented code following the repo's style guidelines.
5. A comprehensive JUnit test file (WaveletTreeTest.java) with various test cases (e.g., small arrays, arrays with duplicate values, out-of-bounds checks).

Additional Information

No response