C++範囲合計クエリと平方根による更新

配列といくつかのクエリが与えられます。また、クエリには2つのタイプがあります。つまり、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）になります。効率的なアプローチを探しましょう。

効率的なアプローチ

操作の数または反復の数を減らすと、プログラムが効率的になる可能性があります。配列を作成し、更新と合計のクエリに2つの関数を使用する、バイナリインデックスツリーを使用できます。更新クエリの場合、要素が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、Java、Pythonなどのプログラミング言語で実行できるこの問題のC++プログラムについても説明しました。このチュートリアルがお役に立てば幸いです。