Answer Repeated Range Aggregate Queries on a Static BST

Problem

A fixed binary search tree has been converted once by an in-order traversal into the JSON-portable array sortedValues, which is sorted in nondecreasing order and repeats duplicate node values. Given queries, where each query is [low, high], return one [sum, count] pair per query for all values in that inclusive range. Return [0, 0] for an empty range result. Preprocess the fixed array so repeated queries do not scan all values.

Constraints & Assumptions

• 0 <= len(sortedValues) <= 200,000, and duplicate values appear once per BST node.
• There are at most 200,000 queries.
• Values and range bounds are 32-bit signed integers.
• Use signed 64-bit prefix sums in Java and C++; the stated bounds keep every sum within +/-2^53, so Python integers and JavaScript numbers are exact as well.

Clarifications

• Range endpoints are inclusive and low <= high.
• Duplicates contribute separately to both sum and count.
• The public function receives sortedValues and queries; it does not receive or construct a custom tree-node type.
• Return results in the same order as the queries, and let the caller compute an average as sum / count when count is nonzero.

Examples

sortedValues = [1, 3, 3, 5, 8]
queries = [[3, 5], [6, 7]]
output = [[11, 3], [0, 0]]

Hints