C++での範囲合計のカウント
整数の配列numsがあるとすると、範囲[下限、上限]の両方を含む範囲の合計の数を見つける必要があります。範囲の合計S(i、j)は、インデックスiからインデックスjまでのnumsの要素の合計として定義されます。ここでi≤jです。
したがって、入力が[-3,6、-1]、lower =-2、upper =2の場合、範囲は[0,2]、合計は2、[2、 2]、合計は-2です。
これを解決するには、次の手順に従います-
- 関数mergeIt()を定義します。これは、配列プレフィックス、start、mid、end、lower、upper、 を取ります。
- i:=start、j:=mid + 1
- temp:=end --start + 1
- 低:=中+ 1、高:=中+ 1
- k:=0
- サイズの配列arrを定義します:temp。
- i <=midの間、-
- を実行します
- while(low <=end and prefix [low] --prefix [i]
- 最低値を1つ増やします
- while(low <=end and prefix [low] --prefix [i]
- while(high <=end and prefix [high] --prefix [i] <=upper)、do −
- 高さを1つ増やします
- while(j <=end and prefix [j]
- arr [k]:=prefix [j]
- (jを1増やします)
- (kを1増やします)
- を実行します
- arr [k]:=prefix [j]
- (kを1増やします)
- (jを1増やします)
- を取ります。
- start> =endの場合、戻る
- prefix [i]:=prefix [i-1] + nums [i-1]
理解を深めるために、次の実装を見てみましょう-
例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int count = 0;
void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){
lli i = start, j = mid + 1;
lli temp = end - start + 1;
lli low = mid + 1, high = mid + 1;
lli k = 0;
lli arr[temp];
while(i <= mid){
while(low <= end && prefix[low] - prefix[i] < lower) low++;
while(high <= end && prefix[high] - prefix[i] <= upper) high++;
while(j<= end && prefix[j] < prefix[i]){
arr[k] = prefix[j];
j++;
k++;
}
arr[k] = prefix[i];
i++;
k++;
count += high - low;
}
while(j <= end){
arr[k] = prefix[j];
k++;
j++;
}
for(i = 0; i < temp; i++){
prefix[start] = arr[i];
start++;
}
}
void merge(lli prefix[], lli start, lli end, lli lower, lli upper){
if(start >= end)return;
lli mid = start + (end - start) / 2;
merge(prefix, start, mid, lower, upper);
merge(prefix, mid + 1, end, lower, upper);
mergeIt(prefix, start, mid, end, lower, upper);
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
lli n = nums.size();
count = 0;
lli prefix[n + 1];
prefix[0] = 0;
for(lli i = 1; i <= n; i++){
prefix[i] = prefix[i - 1] + nums[i - 1];
}
merge(prefix, 0, n, lower, upper);
return count;
}
};
main(){
Solution ob;
vector<int> v = {-3,6,-1};
cout << (ob.countRangeSum(v, -2, 2));
} 入力
{-3,6,-1}
-2
2 出力
2
-
Range Sum Query2D-C++では不変
matrixと呼ばれる2D行列があるとすると、(row1、col1)を使用して左上隅で定義され、(row1、col1)を使用して右下隅で定義される長方形内の要素の合計を見つける必要があります。 row2、col2)。 したがって、行列が-のような場合 3 0 1 4 2 5 6 3 2 1 1 2 0 1 5 4 1 0 1 7 1 0 3 0 5 上記の長方形で、(2,1)と(4,3)で定義された青色で、合計8が含まれています。 したがって、sumRegion(
-
範囲合計クエリ-C++の不変
整数の配列があるとします。インデックスiからjまでの要素の合計を見つける必要があります。配列は不変であるため、要素は変更されず、そのようなクエリが複数存在することに注意する必要があります。そのため、多数のクエリの実行時間を気にする必要があります。配列がA=[5、8、3、6、1、2、5]のようであるとすると、クエリが(A、0、3)の場合、5 + 8 + 3 + 6=22になります。 これを解決するには、次の手順に従います- 1つの配列Bを取得します。B[i]は0からiまでの要素の合計を格納します クエリの場合は、B [j] – B [i – 1]を実行します 理解を深めるために、次の実装