题目描述

给你一个数组 nums，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

样例

输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
输出：13 
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4。
将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]。
下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13。

输入：nums = [1,2,3,4], n = 4, left = 3, right = 4
输出：6
解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]。
下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6。

输入：nums = [1,2,3,4], n = 4, left = 1, right = 10
输出：50

限制

• 1 <= nums.length <= 10^3
• nums.length == n
• 1 <= nums[i] <= 100
• 1 <= left <= right <= n * (n + 1) / 2

算法1

(暴力) $O(n^2 \log n)$

1. 直接按照题目描述暴力，求出所有区间和，然后排序，最后累加答案。

时间复杂度

• 共有 $O(n^2)$ 个区间和，排序的时间复杂度为 $O(n^2 \log n)$，累加答案的时间复杂度为 $O(n^2)$。
• 故总时间复杂度为 $O(n^2 \log n)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储所有区间和。

C++ 代码

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        const int mod = 1000000007;
        vector<int> sums;

        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = i; j < n; j++) {
                s += nums[j];
                sums.push_back(s);
            }
        }

        sort(sums.begin(), sums.end());

        long long ans = 0;
        for (int i = left - 1; i <= right - 1; i++)
            ans += sums[i];

        return ans % mod;
    }
};

算法2

(二分答案，双指针) $O(n \log M)$

1. 求出第 right 个区间和与第 left - 1 个区间和。这一步可以统一看做求出第 m 个区间和。我们可以采用二分答案的方式求解。
   • 假设 mid 为待定的区间和，我们通过双指针，统计出小于等于 mid 的区间和的个数。如果个数大于等于 m，则 r = mid 向下二分。否则 l = mid + 1，向上二分。
   • 设 l 是第 m 个区间和的数值，我们接下来需要求出前 m 个区间和的总和。这需要拆成两部分：求出小于等于 l - 1 的区间和的总和，然后求出等于 l 的区间和总和。
   • 第一部分，求出小于 l 的区间和总和：我们预处理两个数组，一个是前缀和数组 pre，另一个是前缀和阶梯数组 s。其中 pre[i] = pre[i - 1] + nums[i]，s[i] = s[i - 1] + nums[i] * i。两个数组的下标都从 1 开始。有了这两个数组，在双指针的过程中，假设区间 [j, i] 是以 i 为结尾的有效区间，则可以通过这两个数组，计算出区间集合 [j, i], [j + 1, i], ..., [i, i] 的区间和总和。
   • 第二部分，求出等于 l 的区间和总和：先求出有多少个区间的区间和小于等于 l - 1，然后用 m 减去这个个数再乘 l。
2. 最终的答案就是 solve(right) - solve(leflt - 1)。
3. 注意，代码中预处理数组的下标从 1 开始，其余下标都从 0 开始。

时间复杂度

• 二分的时间复杂度为 $O(\log M)$，每次验证双指针仅需要 $O(n)$ 的时间，其中 $M$ 是数组总和。
• 故总时间复杂度为 $O(n \log M)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储预处理的两个数组。

C++ 代码

class Solution {
private:
    #define LL long long
    const int mod = 1000000007;
    const int M = 100000;

    vector<int> s, pre;

    int calc_le(const vector<int> &nums, int n, int mid) {
        int tot = 0;
        LL res = 0;
        for (int i = 0, j = 0; i < n; i++) {
            tot += nums[i];
            while (tot > mid) {
                tot -= nums[j];
                j++;
            }
            res += s[i + 1] - s[j] - j * (pre[i + 1] - pre[j]);
        }

        return res % mod;
    }

    int count_le(const vector<int> &nums, int n, int mid) {
        int tot = 0, counter = 0;
        for (int i = 0, j = 0; i < n; i++) {
            tot += nums[i];
            while (tot > mid) {
                tot -= nums[j];
                j++;
            }
            counter += i - j + 1;
        }

        return counter;
    }

    int solve(const vector<int> &nums, int n, int m) {
        int l = 1, r = M;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (count_le(nums, n, mid) >= m) r = mid;
            else l = mid + 1;
        }

        return (calc_le(nums, n, l - 1) + 
            (LL)(m - count_le(nums, n, l - 1)) * l) % mod;
    }

    void init(const vector<int> &nums, int n) {
        s.resize(n + 1);
        pre.resize(n + 1);
        s[0] = pre[0] = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1] * i;
            pre[i] = pre[i - 1] + nums[i - 1];
        }
    }

public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        init(nums, n);
        return (solve(nums, n, right) - solve(nums, n, left - 1) + mod) % mod;
    }
};