# 間隔之和與除數的更新 > 原文： [https://www.geeksforgeeks.org/sum-interval-update-number-divisors/](https://www.geeksforgeeks.org/sum-interval-update-number-divisors/) 給定一個由 N 個整數組成的數組 A。 您必須回答兩種查詢： 1.更新[l，r] –對于從 l 到 r 范圍內的每個 i，用 D（A _i 來更新 A _i 。 ），其中 D（A _i ）表示 A _i 2 的除數的數量。查詢[l，r] –計算范圍在 l 和之間的所有數字的總和。 輸入為兩個整數 N 和 Q，分別表示數組中的整數數和查詢數。 下一行包含 n 個整數數組，后跟 Q 個查詢，其中第一個查詢表示為 _i ，l _i ，r _i 類型。 **先決條件**： [二叉索引樹](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/) | [段樹](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/) 例子 ： ``` Input : 7 4 6 4 1 10 3 2 4 2 1 7 2 4 5 1 3 5 2 4 4 Output : 30 13 4 ``` **說明**：第一個查詢是計算從 A ₁ 到 A ₇ 的數字總和，即 6 + 4 +1 + 10 + 3 + 2 + 4 =30。類似，第二個查詢結果為 13。對于第三個查詢， 是更新操作，因此 A ₃ 將保持為 1，A ₄ 將變為 4。 A ₅ 將變為 2。 第四個查詢將得出 A ₄ = 4。 **樸素的方法**： 一個簡單的解決方案是運行一個從 l 到 r 的循環，并計算給定范圍內的元素之和。 要更新值，請預先計算每個數字的除數的值，然后簡單地做 arr [i] = divisors [arr [i]]。 **高效方法**： 的想法是減少每個查詢的時間復雜度，并將操作更新為 O（logN）。 使用二進制索引樹（BIT）或段樹。 構造一個 BIT []數組，并具有兩個用于查詢和更新操作的功能，并針對每個數字預先計算除數的數量。 現在，對于每個更新操作，主要觀察到的是數字“ 1”和“ 2”的除數分別為“ 1”和“ 2”，因此，如果它存在于更新查詢的范圍內，則它們不存在。 不需要更新。 我們將使用一個集合來存儲僅大于 2 的那些數字的索引，并使用二分搜索來查找更新查詢的 l 索引并遞增 l 索引，直到在該更新查詢的范圍內每個元素都被更新為止。 如果 arr [i]只有 2 個除數，則在更新后將其從集合中刪除，因為即使在下一次更新查詢之后它也始終為 2。 對于總和查詢操作，只需執行 query（r）– query（l – 1）。 ``` // CPP program to calculate sum? // in an interval and update with // number of divisors #include <bits/stdc++.h> using namespace std; int divisors[100], BIT[100]; // structure for queries with members type,? // leftIndex, rightIndex of the query struct queries { ????int type, l, r; }; // function to calculate the number? // of divisors of each number void calcDivisors() { ????for (int i = 1; i < 100; i++) { ????????for (int j = i; j < 100; j += i) { ????????????divisors[j]++;? ????????} ????} } // function for updating the value void update(int x, int val, int n) { ????for (x; x <= n; x += x&-x) { ????????BIT[x] += val; ????} } // function for calculating the required? // sum between two indexes int sum(int x) { ????int s = 0; ????for (x; x > 0; x -= x&-x) { ????????s += BIT[x];? ????} ????return s; } // function to return answer to queries void answerQueries(int arr[], queries que[], int n, int q) { ????// Declaring a Set ????set<int> s; ????for (int i = 1; i < n; i++) { ????????// inserting indexes of those numbers? ????????// which are greater than 2 ????????if(arr[i] > 2) s.insert(i); ????????update(i, arr[i], n); ????} ????for (int i = 0; i < q; i++) { ????????// update query ????????if (que[i].type == 1) {? ????????????while (true) { ????????????????// find the left index of query in? ????????????????// the set using binary search ????????????????auto it = s.lower_bound(que[i].l); ????????????????// if it crosses the right index of? ????????????????// query or end of set, then break ????????????????if(it == s.end() || *it > que[i].r) break; ????????????????que[i].l = *it; ????????????????// update the value of arr[i] to? ????????????????// its number of divisors ????????????????update(*it, divisors[arr[*it]] - arr[*it], n); ????????????????arr[*it] = divisors[arr[*it]]; ????????????????// if updated value becomes less than or? ????????????????// equal to 2 remove it from the set ????????????????if(arr[*it] <= 2) s.erase(*it); ????????????????// increment the index ????????????????que[i].l++; ????????????} ????????} ????????// sum query ????????else { ????????????cout << (sum(que[i].r) - sum(que[i].l - 1)) << endl; ????????} ????} } // Driver Code int main()? { ????// precompute the number of divisors for each number ????calcDivisors();? ????int q = 4; ????// input array ????int arr[] = {0, 6, 4, 1, 10, 3, 2, 4}; ????int n = sizeof(arr) / sizeof(arr[0]); ????// declaring array of structure of type queries ????queries que[q + 1];? ????que[0].type = 2, que[0].l = 1, que[0].r = 7; ????que[1].type = 2, que[1].l = 4, que[1].r = 5; ????que[2].type = 1, que[2].l = 3, que[2].r = 5; ????que[3].type = 2, que[3].l = 4, que[3].r = 4; ????// answer the Queries ????answerQueries(arr, que, n, q); ????return 0; } ``` **輸出**： ``` 30 13 4 ``` **回答 Q 查詢的時間復雜度為 O（Q * log（N））。** * * * * * *