Search⌘ K
AI Features

Solution: Range Sum of Sorted Subarray Sums

Solution: Range Sum of Sorted Subarray Sums asks you to calculate every contiguous subarray sum, sort them, and return the total from the given one-based range modulo a large prime.

Statement

You are given an integer array nums containing nn positive integers along with left and right. Calculate the sum of its elements for every non-empty continuous subarray of nums. Collect these sums into a new array and sort it in nondecreasing order. This will result in a new array of size n×(n+1)/2n \times (n + 1) /2.

Your task is to return the sum of the elements in this sorted array from the index left to right (inclusive with 1-based indexing).

Note: As the result can be large, return the sum modulo ...