資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 範圍求和查詢和使用平方根的更新
給定一個數組和多個查詢。此外，還存在兩種型別的查詢，即 update[L, R] 表示將 L 到 R 的元素更新為它們的平方根，而 query[L, R] 表示計算 L 到 R 元素的總和。我們假設一個基於 1 的索引陣列，例如：
Input: nums[ ] = { 0, 9, 4, 1, 5, 2, 3 }, Query[ ] = { {1, 1, 3}, {2, 1, 2}, {1, 2, 5}, { 1, 4, 5}}
Output: 14
10
7
1st element of 1st query is 1 means we need to calculate range sum from 1 to 3 i.e 9 + 4 + 1 = 14
1st element of 2nd query is 2 means we need to update range element from 1 to 2 with their square roots now new arr[] array is { 3, 2, 1, 5, 2, 3 }
1st element of 3rd query is 1 means we need to calculate range sum from 2 to 5 i.e 2 + 1 + 5 + 2 = 10
1st element of the 4th query is 1 means we need to calculate the range sum from 4 to 5 i.e 5 + 2 = 7
Input: nums[] = { 0, 3, 2, 4, 16, 2 }, Query[ ] = {{1, 1, 3}, {2, 2, 5}}
Output: 9尋找解決方案的方法
簡單方法
我們可以使用迴圈直到查詢結束，並返回求和查詢的範圍總和，併為更新查詢更新陣列。但是，此程式的時間複雜度將為 O(q * n)。讓我們尋找一種更高效的方法。
高效方法
如果我們減少操作次數或迭代次數，程式效率將會提高。我們可以使用二叉索引樹，在其中我們建立一個數組並使用兩個函式進行更新和求和查詢。對於更新查詢，如果元素為 1，則無需更新它，因為它的平方根將始終為 1。現在，我們可以使用集合來儲存大於 1 的索引，並使用二分查詢來查詢第 L 個索引並遞增它，直到每個範圍元素都被更新。然後檢查更新後的值是否變為 1，如果是，則從集合中刪除該索引，因為它對於任何更新查詢都將始終為 1。
對於求和查詢，我們可以執行 query(R) - query(L-1)。
示例
以上方法的 C++ 程式碼
#include <bits/stdc++.h>
using namespace std;
// Maximum size input array can be
const int m = 200;
// Creating Binary Indexed tree.
int binary_indexed[m + 1];
// for update query
void update_q(int a, int x, int n){
while(a <= n) {
binary_indexed[a] += x;
a += a & -a;
}
}
// Function to calculate sum range.
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]);
// 2-D array for queries.
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++) {
// Inserting indexes in the set of elements that are greater than 1.
if (nums[i] > 1)
s.insert(i);
update_q(i, nums[i], n);
}
for (int i = 0; i < no_query; i++) {
// Checking 0th index for update query or sum query.
if (q[i][0] == 2) {
while (true) {
// Finding the left index using binary search
auto it = s.lower_bound(q[i][1]);
// checking whether it reaches right index.
if (it == s.end() || *it > q[i][2])
break;
q[i][1] = *it;
// updating array element to their square roots.
update_q(*it, (int)sqrt(nums[*it]) - nums[*it], n);
nums[*it] = (int)sqrt(nums[*it]);
//checking if updated value is 1 the removing it from set
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 等程式語言來實現。希望本教程對您有所幫助。
更新於：2021年11月26日
266 次瀏覽
廣告