題目描述

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-of-range-sum

解題思路

我自己其實是沒有什么思路的，只想到了暴力加前綴和，其實也思考了線段樹，但是線段樹求解區間和的速度比前綴和明顯慢很多。

看了題解的第一種解法，并自己實現了一下，爆了一發long long，第二遍就過了，雖然思路不是自己的但是還是很開心的。

決定跟隨官方題解仔細研究一下這道題。

題解一

主要的思路在于考慮解決一個子問題：兩個升序排列的數組$a,b$，求$a[i]<b[j]$的$(i,j)$對數量

實現代碼：

class Solution {
public:typedef long long ll;ll  ans = 0;ll  Lower, Upper;void Merge(vector<ll> &sum, vector<ll> &tmp, int l, int r){if(r - l <= 1) return ;int mid = (l + r) >> 1;Merge(sum, tmp, l, mid);Merge(sum, tmp, mid, r);int pl = mid, pr = mid;int idx = l;while(idx < mid){while(pl < r && sum[pl] < sum[idx] + Lower) ++pl;while(pr < r && sum[pr] <= sum[idx] + Upper) ++pr;ans += pr - pl;++idx;}int  i = l, j = mid;idx = l;while(i < mid || j < r){if(j >= r || i < mid && sum[i] < sum[j]){tmp[idx++] = sum[i++];} else {tmp[idx++] = sum[j++];}}for(int i=l; i<r; ++i){sum[i] = tmp[i];}}int countRangeSum(vector<int>& nums, int lower, int upper) {int n = nums.size();Lower = lower; Upper = upper;vector<long long > sum(n+1, 0);vector<long long > tmp(n+1, 0);for(int i=1; i<=n; ++i){sum[i] = sum[i-1] + nums[i-1];}Merge(sum, tmp, 0, n+1);return ans;}
};