資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式中更新給定索引和查詢區間最大公約數的查詢
在這個問題中，我們給定一個大小為 N 的陣列 arr[] 和 Q 個查詢，這些查詢可以是兩種型別。我們的任務是建立一個程式來解決這些查詢，以更新給定索引並查詢範圍內的最大公約數。
查詢為 -
型別 1 - {1, index, value} - 將給定索引處的元素增加 value。
型別 2 - {2, L, R} - 查詢索引範圍 [L, R] 內元素的最大公約數。
問題描述 - 我們需要找到範圍 [L, R] 內的元素的最大公約數並返回該值。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {5, 1, 7, 3, 8}, Q = 3
Queries: {{2, 2 , 5}, {1, 3, 6}, {2, 2, 5}}輸出
解釋
解決方案方法
解決該問題的一種方法是使用線段樹，線段樹用於預處理陣列的最大公約數。這將減少計算每個查詢的最大公約數的時間。
建立和使用線段樹
我們這裡使用的線段樹是一棵樹，它將陣列的元素儲存為葉子節點，並將元素的最大公約數儲存為內部節點。
程式說明我們解決方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
int calcGcdRangeRec(int* st, int segL, int segR, int L, int R, int currNode) {
if (L <= segL && R >= segR)
return st[currNode];
if (segR < L || segL > R)
return 0;
int mid = (segL + (segR - segL)/2);
int GcdL = calcGcdRangeRec(st, segL, mid, L, R, 2 * currNode + 1) ;
int GcdR = calcGcdRangeRec(st, mid + 1, segR, L, R, 2 * currNode + 2);
return __gcd(GcdL, GcdR);
}
void updateArrayValueRec(int* st, int L, int R, int index, int diff, int currNode) {
if (index < L || index > R)
return;
st[currNode] = st[currNode] + diff;
if (R != L) {
int mid = (L + (R - L)/ 2);
updateArrayValueRec(st, L, mid, index, diff, 2 * currNode + 1);
updateArrayValueRec(st, mid + 1, R, index, diff, 2 * currNode + 2);
}
}
void updateArrayValue(int arr[], int* st, int n, int index, int newVal) {
if (index < 0 || index > n - 1)
cout << "Invalid Input";
else{
int diff = newVal - arr[index];
arr[index] = newVal;
updateArrayValueRec(st, 0, n - 1, index, diff, 0);
}
}
int calcGcdRange(int* st, int n, int L, int R) {
if (L < 0 || R > n - 1 || L > R) {
cout << "Invalid Input";
return -1;
}
return calcGcdRangeRec(st, 0, n - 1, L, R, 0);
}
int constructGcdST(int arr[], int L, int R, int* st, int currNode) {
if (L == R) {
st[currNode] = arr[L];
return arr[L];
}
int mid = (L + (R - L)/2);
int GcdL = constructGcdST(arr, L, mid, st, currNode * 2 + 1);
int GcdR = constructGcdST(arr, mid + 1, R, st, currNode * 2 + 2);
st[currNode] = __gcd(GcdL, GcdR);
return st[currNode];
}
int main() {
int arr[] = { 1, 3, 6, 9, 9, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[3][3] = {{2, 1, 3}, {1, 1 , 10}, {2, 1, 3}};
int value = (int)(ceil(log2(n)));
int size = 2 * (int)pow(2, value) - 1;
int* st = new int[size];
constructGcdST(arr, 0, n - 1, st, 0);
for(int i = 0; i < n; i++){
if(query[i][0] == 1){
cout<<"Query "<<(i + 1)<<": Updating Values!\n";
updateArrayValue(arr, st, n, query[i][1], query[i][2]);
}
if(query[i][0] == 2)
cout<<"Query "<<(i + 1)<<": GCD is "<<calcGcdRange(st, n, query[i][1], query[i][2])<<endl;
}
return 0;
}輸入
Query 1: GCD is 3 Query 2: Updating Values! Query 3: GCD is 1
更新於: 2020-12-22
193 次瀏覽
廣告