විමසීම්වලින් පසුව පවා සංඛ්‍යා එකතුව


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇත්ත වශයෙන්ම
අරා

ගැටළු ප්රකාශය

මෙම ගැටලුවේදී අපට ලබා දී ඇත්තේ අ අරාව පූර්ණ සංඛ්‍යා හා අරා වල විමසුම්. සඳහා විමසුම, අපට පරාමිති දෙකක් ඇත, දර්ශකය සහ val. සෑම විමසුමකටම පසුව, අපි එකතු කරමු වෝල් අරාව කිරීමට [දර්ශකය]. සියල්ලන්ගේ එකතුව සොයාගත යුතුයි පවා සෑම විමසුමකටම පසුව අරාවෙහි ඇති පූර්ණ සංඛ්‍යා, එය පූර්ණ සංඛ්‍යා දෛශිකයක් ලෙස ආපසු එවන්න.

උදාහරණයක්

A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
8 6 2 4
A = [1,2,3,4], queries = [[2,0],[-2,2],[6,0],[4,2]]
6 6 6 6

ප්රවේශය

විමසීම් වලින් පසුව පවා සංඛ්‍යා එකතුව ක්‍රියාත්මක කිරීම

එක් මූලික ප්‍රවේශයක් වනුයේ:

එක් එක් විමසුම සඳහා, අනුරූපී මූලද්‍රව්‍යය යාවත්කාලීන කරන්න, ඉන්පසු සියලු ඉරට්ටේ සංඛ්‍යා හරහා එකතුව සොයා මුළු අරාව හරහා ගමන් කරන්න. නමුත්, මෙම ප්‍රවේශය O (N * Q) වෙත යොමු වන සෑම විමසුමකටම O (N) කාලය ගතවනු ඇත.

නඩත්තු කිරීමෙන් අපට වඩා හොඳින් කළ හැකිය පෙර මුදල එය අරාවෙහි ඇති සියලුම ඉරට්ටේ සංඛ්‍යා වල එකතුවයි. එක් එක් විමසුම සඳහා, එහි දර්ශකයේ මූලද්‍රව්‍යය දායක වූයේ දැයි අපට පරීක්ෂා කළ හැකිය පවා එකතුව කලින් ගණනය කර ඇත (A [දර්ශකය]% 2 == 0 දැයි පරීක්ෂා කිරීමෙන්). ඔව් නම්, අපි එය ධාවන එකතුවෙන් අඩු කර A [දර්ශකය] A [දර්ශකය] + අගය ලෙස යාවත්කාලීන කරමු. ඊට පසු, A [දර්ශකය] ඉරට්ටේ දැයි අප නැවත පරීක්ෂා කළ යුතුය. ඔව් නම්, අපි එයට එකතු කරමු even_sum. අනෙක් සියලුම මූලද්‍රව්‍යයන් කිසිදු බලපෑමකින් තොරව පවතින බැවින් එම විමසුමට මෙය පිළිතුර වනු ඇත. එබැවින්, අපි සෑම විමසුමකටම O (1) වේලාවට පිළිතුරු දෙමු.

සී ++ වැඩසටහන

#include <bits/stdc++.h>

using namespace std;

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
    int evenSum = 0;

    for(int &x : A) {
        if(x % 2 == 0) {
            evenSum += x;
        }
    }

    int n = queries.size() , val , idx;
    vector <int> ans(n);
    for(int i = 0 ; i < n ; i++) {
        val = queries[i][0] , idx = queries[i][1];
        if(A[idx] % 2 == 0) evenSum -= A[idx];
        A[idx] += val;
        if(A[idx] % 2 == 0) evenSum += A[idx];
        ans[i] = evenSum;
    }

    return ans;
}

int main() {
    vector <int> A = {1 , 2 , 3 , 4};
    vector < vector <int> > queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
    vector <int> ans = sumEvenAfterQueries(A , queries);
    for(int &x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

ජාවා වැඩසටහන

class sum_even_after_queries {
    public static void main(String args[]) {
        int[] A = {1 , 2 , 3 , 4};
        int[][] queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
        int[] ans = sumEvenAfterQueries(A , queries);
        for(int x : ans)
            System.out.print(x + " ");
        System.out.println();
    }

    public static int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int evenSum = 0;

        for(int x : A) {
            if(x % 2 == 0) {
                evenSum += x;
            }
        }
        int n = queries.length , val , idx;
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++) {
            val = queries[i][0];
            idx = queries[i][1];

            if(A[idx] % 2 == 0) evenSum -= A[idx];
            A[idx] += val;
            if(A[idx] % 2 == 0) evenSum += A[idx];
            ans[i] = evenSum;
        }

        return ans;
    }
}
8 6 2 4

විමසීම්වලින් පසුව පවා සංඛ්‍යා එකතුවක සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (N + Q), එහිදී, දී ඇති අරාවේ ප්‍රමාණය N = ප්‍රමාණය. Q = විමසුම් ගණන. අපි එය සොයා ගැනීමට O (N) කාලය ගත කරමු පවා එකතුව සහ සෑම විමසුමකටම පිළිතුරු දීමට O (Q) කාලය.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1), අපි නිරන්තර මතක අවකාශය භාවිතා කරන බැවින්.