327.?區間和的個數

給定一個整數數組 nums，返回區間和在 [lower, upper] 之間的個數，包含 lower 和 upper。
區間和 S(i, j) 表示在 nums 中，位置從 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

說明:
最直觀的算法復雜度是 O(n^2) ，請在此基礎上優化你的算法。

示例：

輸入: nums = [-2,5,-1], lower = -2, upper = 2,
輸出: 3
解釋: 3個區間分別是: [0,0], [2,2], [0,2]，它們表示的和分別為: -2, -1, 2。

***************** ? ?? 前綴和 ?? *******************

區間和問題，一般可以聯想到前綴和

對于數組nums[n]，其前綴和為：

sum[i]=sum[i-1]+nums[i-1]

(sum[0]=0; sum[1]=nums[0]; sum[2]=nums[0]+nums[1])

解法1： ?? 暴力法

對于每一個i，求區間[0，i-1]，[1，i-1]，……，[i-1，i-1]是否滿足條件

class Solution {public: int countRangeSum(vector<int>& nums, int lower, int upper) { int len=nums.size(); vector<int> Sum(len+1,0); int presum=0,cnt=0; for(int i=1;i<=len;i++) { presum += nums[i-1]; for(int j=1;j<=i;j++) { if(presum-Sum[j-1]>=lower && presum-Sum[j-1]<=upper) cnt++; } Sum[i]=presum; } return cnt; }};

時間復雜度：O(n^2)
空間復雜度：O(n)，Sum數組用來存儲前綴和。

解法2：? 樹狀數組

用來解決動態前綴和問題，解決區間加/單點查詢問題

查詢復雜度為O(logN)

Lowbit函數：返回值是 入參轉化為二進制后，最后一個1的位置所代表的數值。

C1, C3, C5, C7的下標的二進制表示 最后一位都是1，放在第一層；C2, C6的下標的二進制表示都為10，放在第二層。

子節點和其父節點的關系：

子節點下標X + lowbit(X) = 父節點下標 Y

舉例：2+lowbit(2)=4;? 3+lowbit(3)=4

修改單點的值，只需要更新覆蓋其值的數組元素就行啦。舉例，修改單點A2，則需要更新C2, C4, C8, C16的值(注意這里4是2+lobit(2), 8是4+lobit(4))。

故修改單點值的代碼

void?add(int?x,int?delta){????while(x<=n)//n為樹狀數組的長度????{???? C[x]+=delta;???? x+=lowbit(x);????}}

查詢前綴和

舉例，計算Sum13=A1+A2+……+A13

只需要計算C13+C12+C8

C13, ?C12 , C8 可以理解為：13 ? ? ....... ? 二進制表示為? 1101

lowbit(13)=1, 13-lowbit(13)=12? ....... ??二進制表示為? 1100

lowbit(12)=4, 12-lowbit(12)=8 ?? ....... ??二進制表示為? 1000

故查詢前綴和的代碼

int query(int x){ int res=0; while(x) {????????res+=C[x];//C[x]為樹狀數組元素 x-=lowbit(x); } return res;}

樹狀數組的初始化：

public FeWickTree(int n){ this.len=n; this.tree=new int[n+1];}public FeWickTree(int[] nums){????this.len=nums.length;????this.tree=new?int[this.len+1];????for(int i=0;i<this.len;i++)????{???? update(i,nums[i]);????}}void update(int i,int delta){ while(i<=this.len) { tree[i]+=delta; i+=lowbit(i); }}

此題樹狀數組題解：

typedef long long LL;class Solution {public: vector data; vector<int> tr; // 查找小于等于x的第一個數的下標，找不到返回0 int binary_search1(LL x) { int l = 0, r = data.size() - 1; while (l < r) { int mid = l + r + 1 >> 1; if (data[mid] <= x) l = mid; else r = mid - 1; } if (l == 0 && data[0] > x) return 0; else return l + 1; } // 查找小于x的第一個數的下標，找不到返回0 int binary_search2(LL x) { int l = 0, r = data.size() - 1; while (l < r) { int mid = l + r + 1 >> 1; if (data[mid] < x) l = mid; else r = mid - 1; } if (l == 0 && data[0] >= x) return 0; else return l + 1; } int lowbit(int x) { return x & -x; } int find(int x) { int ans = 0; for (int i = x; i; i -= lowbit(i)) ans += tr[i]; return ans; } void add(int x, int c) { int n = tr.size() - 1; for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; } int countRangeSum(vector<int>& nums, int lower, int upper) { int n = nums.size(); LL sum = 0; vector s(n); for (int i = 0; i < n; i ++) { sum += nums[i]; s[i] = sum; } data = s; data.push_back(0); sort(data.begin(), data.end()); data.erase(unique(data.begin(), data.end()), data.end()); tr = vector<int>(data.size() + 1); int ans = 0; int idx_zero = binary_search1(0); add(idx_zero, 1); for (auto x : s) { LL a = x - upper, b = x - lower; int idxa = binary_search2(a), idxb = binary_search1(b); int idxx = binary_search1(x); if (idxb != 0) { if (idxa == 0) ans += find(idxb); else ans += find(idxb) - find(idxa); } add(idxx, 1); } return ans; }};

解法3： ? 歸并排序

前置知識點：求逆序對

對于數組a，若對于ia[j]。則a[i]與a[j]構成逆序對。

求解逆序對個數經典的解法是歸并排序。思路如下：

對于數組a[low,high)，若 a[low,mid) 和 a[mid,high) 都已歸并有序，則

對于左半區間 a[low,mid) 的每個元素a[left]，計算 a[mid,high) 有多少個元素小于它。實現的代碼模板如下：

//O(n),其中 n=hi-loint?right=mid;for(int?left=low;left{????//向右移動right指針，直到 a[right]>=a[left]????while(right!=high && a[left]>a[right])???? right++;????//比a[left]小的元素有 right-mid 個????count += right-mid;}//因為左半區間和右半區間都已經歸并，因此?left?越往右越大//故?right?無需每次都從?mid?開始

求解此題時，分兩步：

1)求前綴和得到sums

2)計算前綴和數組中，當 i < j 時，sums[j]-sums[i]的值在[lower,higher]之間。

求解逆序對的個數是該題的一個特例，也就是計算nums[j]-nums[i]<0的個數。

class Solution {public: void mergeResult(vector<int>& sums,int lo,int hi,int mid)//歸并部分代碼實現{ vector<int> tmp(hi-lo,0); int k=0,left=lo,right=mid; while(left { if(sums[left] tmp[k++]=sums[left++]; else tmp[k++]=sums[right++]; } if(left==mid) { while(right tmp[k++]=sums[right++]; } if(right==hi) { while(left tmp[k++]=sums[left++]; } for(int i=lo,m=0;i sums[i]=tmp[m++]; } int merge_sort(vector<int>& sums,int lo,int hi,int lower,int upper){ if(hi-lo<=1) return 0; int mid=(lo+hi)>>1; int count=merge_sort(sums,lo,mid,lower,upper)+merge_sort(sums,mid,hi,lower,upper); int right1=mid,right2=mid; for(int left=lo;left { // 統計右側-nums[left] < lower 的個數 while(right1!=hi && sums[right1]-sums[left] right1++;????????????// 統計右側-nums[left] <= upper 的個數 while(right2!=hi && sums[right2]-sums[left]<=upper) right2++; ????????????//?因此右側-nums[left]的差在?[lower,upper]?的個數為：????????????//count += (right2 - mid) - (right1 - mid); 可以簡寫為下面這樣： count += right2-right1; }????????//該函數可以C++函數替換(inplace_merge 原地歸并)????????//inplace_merge(nums.begin() + lo, nums.begin() + mid, nums.begin() + hi); mergeResult(sums,lo,hi,mid); return count; } int countRangeSum(vector<int>& nums, int lower, int upper) { int len=nums.size(); vector<int> sums(len+1,0); for(int i=1;i<=len;i++) { //計算前綴和 sums[i]=sums[i-1]+nums[i-1]; } return merge_sort(sums,0,len+1,lower,upper); }};

解法4：? 前綴和+線段樹

用線段樹可將時間復雜度降至為O(NlogN)。題目要求lower<=sum(i, j)<= upper，sum(i, j)=prefixsum(j) -?prefixsum(i-1)，那么lower+prefixsum(i-1)<=prefixsum(j)<=upper+prefixsum(i-1)。所以利用前綴和將區間和轉換成了前綴和在線段樹中 query 的問題，只不過線段樹中父節點中存的不是子節點的和，而是子節點出現的次數。另外，由于前綴和會很大，所以需要離散化。舉例，prefixsum=[-3,-2,-1,0]，用前綴和下標進行離散化，所以線段樹中左右區間變成[0,3]。

注意：prefixsum 計算完后需要去重，去重后并排序，方便構造線段樹。最后一步往線段樹中倒敘插入 prefixsum 的時候，用的是非去重的。例如往線段樹中插入prefixsum[5]，query操作實際是做區間匹配，即lower<=sum(i, j)<=upper

舉例：nums[6]=[-3, 1, 2, -2, 2, -1]，lower=-3, upper=-1, prefixsum=[-3, -2, 0, -2, 0, -1]，去重以后并排序得到sum=[-3,-2,-1,0]。離散化構造線段樹，此處展示的是非離散化的線段樹構造。

倒序插入prefixsum[5]=-1，

這時查找區間為[-3+prefixsum[5-1], -1+prefixsum[5-1]]=[-3,-1]。此時滿足等式的只有 j=5，故此步res=1。

倒序插入prefixsum[4]=0，

這時查找區間為[-3+prefixsum[4-1], -1+prefixsum[4-1]]=[-5,-3]。此時沒有滿足等式的情況，故此步res=0。

倒序插入prefixsum[3]=-2，

這時查找區間為[-3+prefixsum[3-1], -1+prefixsum[3-1]]=[-3,-1]。此時滿足等式的情況有 j=3 和 j=5，故此步res=2。

一次類推，一直計算到 插入prefixsum[0]的情況，最后的結果為各步res之和。

總結

以上是生活随笔為你收集整理的树状数组求逆序对_区间和的个数（树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。