Запыт дыяпазону з выкарыстаннем разрэджанай табліцы


Узровень складанасці серада
Часта пытаюцца ў амазонка Publicis Sapient 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, гэта 25.

Запыт дыяпазону з выкарыстаннем разрэджанай табліцы

Алгарытм

  1. Пабудуйце разрэджаную табліцу, выкарыстоўваючы 2d-матрыцу.
  2. Перабярыце масіў і адзначце кожны радок sparse_table у масіў [i].
  3. Перамясціць масіў укладзена і абнавіць значэнне sparse_table як суму разрэджанай табліцы папярэдняга слупка і ў sparse_table [i + 2 J-1 ] [j-1] і захавайце яго ў sparse_table [i] [j].
  4. Для кожнага запыту, які трэба вырашыць, мы атрымліваем налева і направа, усталёўваем значэнне вываду ў 0.
  5. Перабярыце масіў з 16 на 0 і праверце, ці левы + 2j -1 менш, чым роўна правільна, калі праўда,
    1. Дадайце значэнне вываду да sparse_table [злева] [j] і захавайце суму ў вывадзе.
    2. Абнавіце значэнне злева налева + 2
  6. Вяртае значэнне вываду.

Тлумачэнне для запыту сумы дыяпазону з выкарыстаннем разрэджанай табліцы

Дадзены масіў і запыт. Даведайцеся суму ўсіх цэлых лікаў, якая ўваходзіць у дыяпазон запыту. Мы будзем выкарыстоўваць рэдкую канцэпцыю стала. Мы будзем будаваць рэдкі стол. Разрэджаная табліца - гэта 2d-матрыца, у якой мы збіраемся выканаць некаторыя аперацыі і захаваць значэнні ў разрэджанай табліцы.

Абвясціце 2d матрыца. Мы прынялі абмежаванне ў адзін радкоў і не больш за 16 слупкоў у кожным. Мы асабліва ўзялі тут лік 16, бо пасля гэтага атрымаем лік, большае за 2, узняты да ступені 5, таму 16 дастаткова. Потым пасля пяройдзем да першага этапу пабудовы рэдкага стала. Мы збіраемся адзначыць або абнавіць значэнні ў разрэджанай табліцы як дадзены элемент масіва падчас перамяшчэння па масіве. Затым укладзеныя мы збіраемся прайсці масіў, зноў да k колькасці радкоў. Абнавіце разрэджаную табліцу ў i, j у выглядзе сумы разрэджанай табліцы ў i, j-1 і разрэджанай табліцы ў i + 2J-1, j-1. Гэта будзе апошняе неабходнае абнаўленне для разрэджанай табліцы.

Для кожнага запыту, дадзенага як левы, правы дыяпазон, нам трэба перайсці масіў, але перад гэтым усталюйце значэнне вываду на 0. Перабярыце масіў ад 16 да 0, каб мы маглі кожны раз атрымліваць паўнамоцтвы з пункту гледжання 2. 1 <

Рэалізацыя

Праграма C ++ для запыту Range Sum з выкарыстаннем разрэджанай табліцы

#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

Праграма Java для запыту Range Sum з выкарыстаннем разрэджанай табліцы

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)) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

O (n * часопіс (n)) дзе "П" - колькасць элементаў у масіве.

Спасылка