没有更新范围查询的C ++程序？

  • Z时代
  • 2024-01-10
  • 分类：综合

我们需要计算从索引i到索引j的元素总和。由i和j索引值组成的查询将被多次执行。

Input:arr[] = {5, 6, 3, 4, 1 } i = 1, j =3
Output: 13

说明


6 + 3 + 4 = 13
sum[] = {5, 6+5, 3+6+5, 4+3+6+5, 1+4+3+6+5 }
sum[]={5,11,14,18,19}
sum[j]-sum[i-1]=sum[3]-sum[1-1]= sum[3]-sum[0]=18-5=13

逻辑从开始循环索引i到循环j索引并总结这些索引之间的元素是非常基本的。但是我们不能将它们存储在额外的变量中，因此我们将使用另一个数组，在该数组中将数组元素与最后一个数组元素相加，依此类推。然后从j索引上减去i-1索引值；

示例

#include <iostream>
using namespace std;
int rangeSum(int i, int j, int sum[]) {
   if (i == 0)
      return sum[j];
   return sum[j] - sum[i - 1];
}
int main() {
   int arr[] = { 5, 6, 3, 4, 1 };
   int n=5;
   int sum[5];
   sum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      sum[i] = arr[i] + sum[i - 1];
   }
   cout << rangeSum(1, 3, sum) << endl;
   return 0;
}

输出结果

13

以上是 没有更新范围查询的C ++程序？ 的全部内容， 来源链接： utcz.com/z/345586.html

回到顶部