വിരളമായ പട്ടിക ഉപയോഗിച്ച് ശ്രേണി തുക അന്വേഷണം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ പബ്ലിസിസ് സാപിയന്റ് Zoho
അറേ

വിരളമായ പട്ടിക പ്രശ്‌നം ഉപയോഗിച്ചുള്ള ശ്രേണി സംഖ്യയിൽ ഞങ്ങൾക്ക് ഒരു ശ്രേണി അന്വേഷണമുണ്ട്, ഒപ്പം ഒരു പൂർണ്ണസംഖ്യയും നൽകി ശ്രേണി. ശ്രേണിയിൽ വരുന്ന എല്ലാ പൂർണ്ണസംഖ്യകളുടെ ആകെത്തുക കണ്ടെത്തുക എന്നതാണ് തന്നിരിക്കുന്ന ചുമതല.

ഉദാഹരണം

ഇൻപുട്ട്:

arr [] = {1,4,6,8,2,5}

ചോദ്യം: {(0, 3), (2, 4), (1, 5)}

ഔട്ട്പുട്ട്:

19 16 25

വിശദീകരണം: ശ്രേണി 0, 3 ഉൾപ്പെടെ വരുന്ന പൂർണ്ണസംഖ്യകളുടെ ആകെത്തുക 1 + 4 + 6 + 8 ആണ്. വീണ്ടും, ശ്രേണി 19, 2 ശ്രേണിയിൽ വരുന്ന പൂർണ്ണസംഖ്യകളുടെ ആകെത്തുക 4 + 6 + 8 2 ആണ്. പൂർണ്ണസംഖ്യകളുടെ ആകെത്തുക അത് ശ്രേണി 16 ൽ വരുന്നു, 1 ഉൾപ്പെടെ 5 + 4 + 6 + 8 + 2 5 ആണ്.

വിരളമായ പട്ടിക ഉപയോഗിച്ച് ശ്രേണി തുക അന്വേഷണം

അൽഗോരിതം

  1. 2 ഡി മാട്രിക്സ് ഉപയോഗിച്ച് വിരളമായ പട്ടിക നിർമ്മിക്കുക.
  2. അറേയിലൂടെ സഞ്ചരിച്ച് വിരള_ടേബിളിന്റെ എല്ലാ വരികളും അറേയിലേക്ക് അടയാളപ്പെടുത്തുക [i].
  3. അറേ നെസ്റ്റലായി സഞ്ചരിക്കുക, മുമ്പത്തെ നിരയുടെ വിരള പട്ടികയുടെ ആകെത്തുകയായി സ്പാർസ്_ടേബിൾ മൂല്യം അപ്ഡേറ്റ് ചെയ്യുക, സ്പാർസ്_ടേബിൾ [i + 2 j-1 ] [j-1] എന്നിട്ട് അത് വിരളമായ ടേബിളിൽ സംഭരിക്കുക [i] [j].
  4. പരിഹരിക്കാനുള്ള ഓരോ ചോദ്യത്തിനും, ഞങ്ങൾ ഇടത്തോട്ടും വലത്തോട്ടും പോയി output ട്ട്‌പുട്ടിന്റെ മൂല്യം 0 ആയി സജ്ജമാക്കുക.
  5. അറേ 16 മുതൽ 0 വരെ സഞ്ചരിക്കുക, ഇടത് + 2 ആണോയെന്ന് പരിശോധിക്കുകj -1 ശരിക്ക് തുല്യമായതിനേക്കാൾ കുറവാണ്, ശരിയാണെങ്കിൽ,
    1. Sp ട്ട്‌പുട്ടിന്റെ മൂല്യം sparse_table [ഇടത്] [j] ലേക്ക് ചേർത്ത് തുക .ട്ട്‌പുട്ടിലേക്ക് സംഭരിക്കുക.
    2. ഇടത് നിന്ന് ഇടത്തേക്ക് + 2 അപ്‌ഡേറ്റ് ചെയ്യുക
  6. .ട്ട്‌പുട്ടിന്റെ മൂല്യം നൽകുക.

വിരളമായ പട്ടിക ഉപയോഗിച്ച് റേഞ്ച് സം ചോദ്യത്തിനുള്ള വിശദീകരണം

ഒരു ശ്രേണിയും ചോദ്യവും നൽകി. ഒരു അന്വേഷണത്തിൽ ഒരു പരിധിക്കുള്ളിൽ വരുന്ന എല്ലാ സംഖ്യകളുടെ ആകെത്തുക കണ്ടെത്തുക. ഞങ്ങൾ വിരളമായ പട്ടിക ആശയം ഉപയോഗിക്കും. ഞങ്ങൾ ഒരു വിരളമായ പട്ടിക നിർമ്മിക്കും. വിരള പട്ടിക 2 ഡി മാട്രിക്സാണ്, അതിൽ ഞങ്ങൾ ചില പ്രവർത്തനങ്ങൾ നടത്താനും മൂല്യങ്ങൾ ഒരു വിരള പട്ടികയിൽ സൂക്ഷിക്കാനും പോകുന്നു.

ഒരു 2 ഡി പ്രഖ്യാപിക്കുക മാട്രിക്സ്. ഞങ്ങൾ ഒരു ലക്ഷം വരികളും പരമാവധി 16 നിരകളും വീതമുണ്ട്. ഞങ്ങൾ ഇവിടെ പ്രത്യേകിച്ചും 16-ാം നമ്പർ എടുത്തിട്ടുണ്ട്, കാരണം അതിനുശേഷം പവർ 2 ലേക്ക് ഉയർത്തിയ 5-നേക്കാൾ വലിയ ഒരു സംഖ്യ നമുക്ക് ലഭിക്കും, അതിനാൽ 16 മതി. അതിനുശേഷം ഒരു വിരളമായ പട്ടിക നിർമ്മിക്കുന്നതിന്റെ ആദ്യ ഘട്ടത്തിലേക്ക് കടക്കും. അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ ഞങ്ങൾ നൽകിയ അറേ ഘടകമായി വിരള പട്ടികയിൽ മൂല്യങ്ങൾ അടയാളപ്പെടുത്താനോ അപ്‌ഡേറ്റ് ചെയ്യാനോ പോകുന്നു. നെസ്റ്റഡ് ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കാൻ പോകുന്നു, വീണ്ടും k വരികളുടെ എണ്ണം വരെ. I, j-1 എന്നതിലെ വിരള പട്ടികയും i + 2 ലെ വിരള പട്ടികയുടെ ആകെത്തുകയായി അപ്‌ഡേറ്റ് ചെയ്യുക.j-1, ജെ -1. വിരളമായ പട്ടികയ്‌ക്ക് ആവശ്യമായ അന്തിമ അപ്‌ഡേറ്റായിരിക്കും ഇത്.

ഇടത്, വലത് ശ്രേണി എന്ന് നൽകിയിരിക്കുന്ന ഓരോ ചോദ്യത്തിനും, ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കേണ്ടതുണ്ട്, പക്ഷേ അതിനുമുമ്പ് output ട്ട്‌പുട്ടിന്റെ മൂല്യം 0 ആയി സജ്ജമാക്കുക. അറേ 16 മുതൽ 0 വരെ സഞ്ചരിക്കുക, അങ്ങനെ ഓരോ തവണയും 2 ന്റെ അടിസ്ഥാനത്തിൽ നമുക്ക് അധികാരങ്ങൾ ലഭിക്കും. 1 <

നടപ്പിലാക്കൽ

വിരള പട്ടിക ഉപയോഗിച്ച് റേഞ്ച് സം ചോദ്യത്തിനായുള്ള സി ++ പ്രോഗ്രാം

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

void SparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sparse_table[i][0] = arr[i];

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

    cout << solveQuery(0, 3) << endl;
    cout << solveQuery(2, 4) << endl;
    cout << solveQuery(1, 5) << endl;

    return 0;
}
19
16
25

വിരളമായ പട്ടിക ഉപയോഗിച്ച് ശ്രേണി സംഖ്യയ്‌ക്കായുള്ള ജാവ പ്രോഗ്രാം

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}
19
16
25

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n * ലോഗ് (n)) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n * ലോഗ് (n)) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

അവലംബം