Segment Statistics Object

Design a class SegmentStats that is built once from a list of integers and then answers many questions about inclusive index ranges.

• SegmentStats(values): store what you need about values.
• total(l, r): return the sum of values[l..r].
• evens(l, r): return how many of values[l..r] are even.

Examples

Input:  ops  = ["SegmentStats", "total", "evens", "total"]
        args = [[[2, 5, 4, 7, 6]], [1, 3], [0, 4], [2, 2]]
Output: [None, 16, 3, 4]
Explanation: 5 + 4 + 7 = 16; the even values 2, 4, 6 all lie in 0..4; values[2] is 4.

Constraints

• 1 <= len(values) <= 10**5, -10**6 <= values[i] <= 10**6
• Up to 10**5 calls of total and evens in total, with 0 <= l <= r < len(values)
• Target: O(n) construction, O(1) per query. Scanning the range on every call is too slow for the largest tests.

Goals

• Do all preprocessing once in the constructor
• Answer two kinds of range queries from separate prefix arrays