చిన్న పట్టికను ఉపయోగించి పరిధి మొత్తం ప్రశ్న


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ పబ్లిసిస్ సపియంట్ జోహో
అర్రే

చిన్న పట్టిక సమస్యను ఉపయోగించి శ్రేణి మొత్తం ప్రశ్నలో మనకు శ్రేణి ప్రశ్న ఉంది మరియు పూర్ణాంకం ఇవ్వబడింది అమరిక. ఇచ్చిన పని ఏమిటంటే పరిధిలో వచ్చే అన్ని పూర్ణాంకాల మొత్తాన్ని తెలుసుకోవడం.

ఉదాహరణ

ఇన్పుట్:

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 25.

చిన్న పట్టికను ఉపయోగించి పరిధి మొత్తం ప్రశ్న

అల్గారిథం

  1. 2 డి మ్యాట్రిక్స్ ఉపయోగించి చిన్న పట్టికను రూపొందించండి.
  2. శ్రేణిలో ప్రయాణించి, స్పార్స్_టేబుల్ యొక్క ప్రతి అడ్డు వరుసను గుర్తించండి [i].
  3. శ్రేణిని సమూహంగా ప్రయాణించి, మునుపటి కాలమ్ యొక్క చిన్న పట్టిక మొత్తంగా మరియు sparse_table [i + 2 వద్ద sparse_table విలువను నవీకరించండి. j-1 ] [j-1] మరియు దానిని స్పార్స్_టేబుల్ [i] [j] లో నిల్వ చేయండి.
  4. పరిష్కరించడానికి ప్రతి ప్రశ్న కోసం, మేము ఎడమ మరియు కుడి వైపుకు వస్తాము, అవుట్పుట్ విలువను 0 గా సెట్ చేస్తాము.
  5. శ్రేణిని 16 నుండి 0 వరకు ప్రయాణించి, ఎడమ + 2 ఉందో లేదో తనిఖీ చేయండిj -1 కుడి కంటే తక్కువ కంటే తక్కువ, నిజమైతే,
    1. అవుట్పుట్ యొక్క విలువను స్పార్స్_టేబుల్ [ఎడమ] [j] కు జోడించి, మొత్తాన్ని అవుట్‌పుట్‌లో నిల్వ చేయండి.
    2. ఎడమ నుండి ఎడమ + 2 విలువను నవీకరించండి
  6. అవుట్పుట్ విలువను తిరిగి ఇవ్వండి.

చిన్న పట్టికను ఉపయోగించి శ్రేణి మొత్తం ప్రశ్నకు వివరణ

శ్రేణి మరియు ప్రశ్న ఇవ్వబడింది. ప్రశ్నలో ఒక పరిధిలో వచ్చే అన్ని పూర్ణాంకాల మొత్తాన్ని కనుగొనండి. మేము చిన్న పట్టిక భావనను ఉపయోగిస్తాము. మేము ఒక చిన్న పట్టికను నిర్మిస్తాము. చిన్న పట్టిక 2d మాతృక, దీనిలో మేము కొన్ని ఆపరేషన్లు చేయబోతున్నాము మరియు విలువలను చిన్న పట్టికలో నిల్వ చేయబోతున్నాము.

2 డి ప్రకటించండి మాత్రిక. మేము లక్ష వరుసల పరిమితిని మరియు గరిష్టంగా 16 నిలువు వరుసలను తీసుకున్నాము. మేము ఇక్కడ ప్రత్యేకంగా 16 సంఖ్యను తీసుకున్నాము, ఎందుకంటే ఆ తరువాత శక్తి 2 కి పెంచబడిన 5 కన్నా ఎక్కువ సంఖ్యను పొందుతాము, కాబట్టి 16 సరిపోతుంది. అప్పుడు చిన్న పట్టికను నిర్మించే మొదటి దశకు చేరుకుంటారు. మేము శ్రేణి గుండా ప్రయాణించేటప్పుడు ఇచ్చిన శ్రేణి మూలకం వలె చిన్న పట్టిక వద్ద విలువలను గుర్తించబోతున్నాము లేదా నవీకరించబోతున్నాము. అప్పుడు సమూహము మేము శ్రేణిని దాటబోతున్నాము, మళ్ళీ k సంఖ్యల వరుసల వరకు. I, j వద్ద చిన్న పట్టికను i, j-1 వద్ద చిన్న పట్టిక మరియు i + 2 వద్ద చిన్న పట్టికను నవీకరించండి.j-1, జ -1. ఇది చిన్న పట్టికకు అవసరమైన చివరి నవీకరణ అవుతుంది.

ఎడమ, కుడి శ్రేణిగా ఇవ్వబడిన ప్రతి ప్రశ్నకు, మేము శ్రేణిని దాటాలి, కాని దీనికి ముందు అవుట్పుట్ విలువను 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 * log (n))  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

O (n * log (n))  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.

సూచన