C++ 范围总和查询以及使用平方根的更新
c++server side programmingprogramming
给定一个数组和几个查询。此外，查询有两种类型，即 update[ L, R ] 表示使用平方根更新从 L 到 R 的元素，而 query[ L, R ] 表示计算从 L 到 R 的元素之和。我们假设一个基于 1 的索引数组，例如
输入:nums[ ] = { 0, 9, 4, 1, 5, 2, 3 }, Query[ ] = { {1, 1, 3}, {2, 1, 2}, {1, 2, 5}, { 1, 4, 5}}
输出:14
10
7
第一个查询的第一个元素是 1，意味着我们需要计算从 1 到 3 的范围和，即 9 + 4 + 1 = 14
第二个查询的第一个元素是 2，意味着我们需要使用平方根更新从 1 到 2 的范围元素现在新的 arr[] 数组是 { 3, 2, 1, 5, 2, 3 }
第三个查询的第一个元素是 1，这意味着我们需要计算从 2 到 5 的范围总和，即 2 + 1 + 5 + 2 = 10
第四个查询的第一个元素是 1，这意味着我们需要计算从 4 到 5 的范围总和，即 5 + 2 = 7
输入:nums[] = { 0, 3, 2, 4, 16, 2 }, Query[ ] = {{1, 1, 3}, {2, 2, 5}}
输出:9
寻找解决方案的方法
简单方法
我们可以使用循环直到查询结束并返回总和查询的范围总和并更新更新查询的数组。但是这个程序的时间复杂度为 O(q * n)。让我们寻找一种有效的方法。
有效的方法
如果我们减少操作次数或迭代次数，程序就会变得高效。我们可以使用二叉索引树，在其中创建一个数组并使用两个函数进行更新和求和查询。对于更新查询，如果元素为 1，则无需更新它，因为它的平方根只有 1。现在我们可以使用一个集合来存储大于 1 的索引，并使用二分搜索来查找第 L 个索引并递增它，直到每个范围元素都更新。然后检查更新后的值是否变为 1，然后从集合中删除该索引，因为对于任何更新查询，它始终为 1。
对于求和查询，我们可以执行 query(R) - query(L-1)。
示例
上述方法的 C++ 代码
#include <bits/stdc++.h>
using namespace std;
// 输入数组的最大大小可以是
const int m = 200;
// 创建二叉索引树。
int binary_indexed[m + 1];
// 用于更新查询
void update_q(int a, int x, int n){
while(a <= n) {
binary_indexed[a] += x;
a += a & -a;
}
}
// 计算总和范围的函数。
int sum_q(int a){
int s = 0;
while(a > 0) {
s += binary_indexed[a];
a -= a & -a;
}
return s;
}
int main(){
int no_query = 4;
int nums[] = { 0, 9, 4, 1, 5, 2, 3 };
int n = sizeof(nums) / sizeof(nums[0]);
// 用于查询的二维数组。
int q[no_query + 1][3];
q[0][0] = 1, q[0][1] = 1, q[0][2] = 3;
q[1][0] = 2, q[1][1] = 1, q[1][2] = 2;
q[2][0] = 1, q[2][1] = 2, q[2][2] = 5;
q[3][0] = 1, q[3][1] = 4, q[3][2] = 5;
set<int> s;
for (int i = 1; i < n; i++) {
// 在大于 1 的元素集合中插入索引。
if (nums[i] > 1)
s.insert(i);
update_q(i, nums[i], n);
}
for (int i = 0; i < no_query; i++) {
// 检查第 0 个索引以进行更新查询或求和查询。
if (q[i][0] == 2) {
while (true) {
// 使用二分查找查找左索引
auto it = s.lower_bound(q[i][1]);
// 检查是否到达右索引。
if (it == s.end() || *it > q[i][2])
break;
q[i][1] = *it;
// 将数组元素更新为其平方根。
update_q(*it, (int)sqrt(nums[*it]) - nums[*it], n);
nums[*it] = (int)sqrt(nums[*it]);
//检查更新后的值是否为 1，然后将其从集合中删除
if (nums[*it] == 1)
s.erase(*it);
q[i][1]++;
}
} else {
cout <<<"query<< i+1 <<": " << (sum_q(q[i][2]) - sum_q(q[i][1] - 1)) << endl;
}
}
return 0;
}
输出
query1: 14 query3: 10 query4: 7
结论
在本教程中，我们讨论了数组的范围总和查询和范围更新查询。我们讨论了解决这个问题的简单方法和使用二叉索引树的有效方法。我们还讨论了这个问题的 C++ 程序，我们可以使用 C、Java、Python 等编程语言来完成。我们希望您觉得本教程有用。
