Сийрэг хүснэгтийг ашиглан Range Sum Query


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Publicis Sapient Zoho
Array

Хүснэгтийн сийрэг бодлогыг ашиглан мужийн нийлбэр асуулгад бид бүхэл тоон өгөгдлийг өгсөн болно массив. Өгөгдсөн даалгавар нь муж дотор ирэх бүхэл тоонуудын нийлбэрийг олох явдал юм.

Жишээ нь

Орц:

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 байна.

Сийрэг хүснэгтийг ашиглан Range Sum Query

Алгоритм

  1. 2d матриц ашиглан сийрэг хүснэгт байгуул.
  2. Массивыг дайрч, сийрэг ширээний бүх мөрийг [i] массив болгон тэмдэглэ.
  3. Массивыг үүрээр дайран өнгөрч, сийрэг хүснэгтийн утгыг өмнөх баганын сийрэг хүснэгтийн нийлбэр болгон шинэчилнэ үү [i + 2 j-1 хувилбар ] [j-1], сийрэг ширээ [i] [j] -д хадгална уу.
  4. Асуулт бүрийг шийдвэрлэхийн тулд бид баруун, зүүн тийш гарч, гаралтын утгыг 0 болгоно.
  5. Массивыг 16-аас 0 хүртэл тойрч, зүүн + 2 эсэхийг шалгана ууj -1 нь баруунтай тэнцүү, хэрэв үнэн бол,
    1. Үр дүнгийн утгыг sparse_table [зүүн] [j] дээр нэмээд нийлбэрийг гаралтад хадгална.
    2. Зүүнээс зүүн тийш утгыг шинэчил + 2
  6. Гаралтын утгыг буцаана.

Сийрэг хүснэгт ашиглан Range Sum Query-ийн тайлбар

Массив ба асуулга өгсөн. Асуулгад багтсан бүхэл тоонуудын нийлбэрийг олж мэд. Бид сийрэг ширээний ойлголтыг ашиглах болно. Бид сийрэг ширээ барих болно. Сийрэг хүснэгт бол 2d матриц бөгөөд бид зарим үйлдлүүдийг хийж, утгыг сийрэг хүснэгтэнд хадгалах болно.

2d тунхагла Матриц. Бид нэг лак мөрийн хязгаар, дээд тал нь 16 багана авсан. Бид энд 16 дугаарыг онцгойлон авч үзсэн тул 2-р түвшинд 5-оос дээш тоог авах тул 16 хангалттай. Дараа нь сийрэг ширээ барих эхний үе шатанд орох болно. Бид массивыг дайран өнгөрөхдөө сийрэг ширээн дээрх утгуудыг өгөгдсөн массивын элемент болгон тэмдэглэх эсвэл шинэчлэх гэж байна. Дараа нь бид массивыг дайран өнгөрч, k тооны мөр хүртэл давтах болно. I, j дээрх сийрэг хүснэгтийг i, j-1 дээрх сийрэг хүснэгтийн нийлбэр, i + 2 дахь сийрэг хүснэгтийн нийлбэр болгон шинэчил.j-1 хувилбар, j-1. Энэ нь сийрэг хүснэгтэд шаардлагатай эцсийн шинэчлэлт болно.

Зүүн, баруун хязгаарт өгсөн асуулга тус бүрт бид массивыг дайран өнгөрөх хэрэгтэй, гэхдээ үүнээс өмнө гаралтын утгыг 0 гэж тохируулах хэрэгтэй. Массивыг 16-аас 0-ээр дамжуулж, ингэснээр бид хүч бүрийг 2 гэсэн утгаар авах боломжтой болно. 1 <

Хэрэгжүүлэх

Sparse Table ашиглан Range Sum Query-д зориулсан C ++ програм

#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

Sparse Table ашиглан Range Sum Query-д зориулсан Java програм

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" массив дахь элементүүдийн тоо юм.

лавлагаа