சிதறிய அட்டவணையைப் பயன்படுத்தி வரம்பு தொகை வினவல்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் பப்ளிஸ் சப்பியண்ட் ஸோகோ
அணி

சிதறல் அட்டவணை சிக்கலைப் பயன்படுத்தி வரம்பு தொகை வினவலில் எங்களிடம் ஒரு வரம்பு வினவல் உள்ளது மற்றும் ஒரு முழு எண் கொடுக்கப்பட்டுள்ளது வரிசை. வரம்பில் வரும் அனைத்து முழு எண்களின் கூட்டுத்தொகையைக் கண்டுபிடிப்பதே கொடுக்கப்பட்ட பணி.

உதாரணமாக

உள்ளீடு:

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. வரிசைக்குச் சென்று, sparse_table இன் ஒவ்வொரு வரிசையையும் வரிசைக்கு குறிக்கவும் [i].
  3. வரிசையை கூட்டாகக் கடந்து, முந்தைய நெடுவரிசையின் சிதறிய அட்டவணையின் கூட்டுத்தொகையாகவும், ஸ்பார்ஸ்_டேபிள் [i + 2] இல் sparse_table மதிப்பைப் புதுப்பிக்கவும். J-1 ] [j-1] மற்றும் அதை sparse_table [i] [j] இல் சேமிக்கவும்.
  4. தீர்க்க ஒவ்வொரு வினவலுக்கும், நாம் இடது மற்றும் வலதுபுறம் சென்று, வெளியீட்டின் மதிப்பை 0 ஆக அமைப்போம்.
  5. வரிசையை 16 முதல் 0 வரை பயணிக்கவும், இடது + 2 என்பதை சரிபார்க்கவும்j -1 என்பது சரி என்றால் சமம், உண்மை என்றால்,
    1. வெளியீட்டின் மதிப்பை sparse_table [இடது] [j] இல் சேர்த்து, தொகையை வெளியீட்டில் சேமிக்கவும்.
    2. இடமிருந்து இடமாக + 2 இன் மதிப்பைப் புதுப்பிக்கவும்
  6. வெளியீட்டின் மதிப்பைத் தரவும்.

சிதறிய அட்டவணையைப் பயன்படுத்தி வரம்பு தொகை வினவலுக்கான விளக்கம்

ஒரு வரிசை மற்றும் வினவல் கொடுக்கப்பட்டுள்ளது. வினவலில் ஒரு வரம்பிற்குள் வரும் அனைத்து முழு எண்களின் கூட்டுத்தொகையைக் கண்டறியவும். நாங்கள் சிதறிய அட்டவணை கருத்தை பயன்படுத்துவோம். நாங்கள் ஒரு சிதறிய அட்டவணையை உருவாக்குவோம். சிதறிய அட்டவணை 2 டி மேட்ரிக்ஸ் ஆகும், இதில் நாம் சில செயல்பாடுகளைச் செய்யப் போகிறோம் மற்றும் மதிப்புகளை ஒரு சிதறல் அட்டவணையில் சேமிக்கப் போகிறோம்.

2d ஐ அறிவிக்கவும் அணி. நாங்கள் ஒரு லட்சம் வரிசைகள் மற்றும் அதிகபட்சம் 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” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

குறிப்பு