សំណួរជួរ Rang Sum Sum ដោយប្រើតារាងរាយប៉ាយ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Publicis Sapient Zoho
អារេ

នៅក្នុងជួរផលបូកជួរដោយប្រើបញ្ហាតារាងរាយប៉ាយយើងមានសំណួរជួរហើយផ្តល់លេខគត់ អារេ។ ភារកិច្ចដែលបានផ្តល់គឺដើម្បីរកផលបូកនៃចំនួនគត់ទាំងអស់ដែលមាននៅក្នុងជួរ។

ឧទាហរណ៍

បញ្ចូល:

មកដល់ [] = {1,4,6,8,2,5}

សំណួរ៖ {(០, ៣), (២, ៤), (១, ៥)}

លទ្ធផល:

19 16 25

ការពន្យល់: ផលបូកនៃចំនួនគត់ដែលមាននៅក្នុងជួរ ០ ៣ បញ្ចូលគ្នាគឺ ១ + ៤ + ៦ + ៨ គឺ ១៩ ។ ជាថ្មីម្តងទៀតផលបូកនៃចំនួនគត់ដែលមាននៅក្នុងជួរ ២ ៤ បញ្ចូលគ្នាគឺ ៦ + ៨ + ២ គឺ ១៦ ផលបូកនៃចំនួនគត់ ដែលមាននៅក្នុងជួរ ១, ៥ បញ្ចូលគ្នាគឺ ៤ + ៦ + ៨ + ២ + ៥ គឺ ២៥ ។

សំណួរជួរ Rang Sum Sum ដោយប្រើតារាងរាយប៉ាយ

ក្បួនដោះស្រាយ

  1. សាងសង់តារាងរាយប៉ាយដោយប្រើម៉ាទ្រីសទី ២ ។
  2. ឆ្លងកាត់អារេហើយសម្គាល់រាល់ជួរដេកនៃ sparse_table ទៅជាអារេ [i] ។
  3. ផ្លាស់ប្តូរអារេនៅខាងចុងនិងធ្វើបច្ចុប្បន្នភាពតម្លៃ sparse_table ជាផលបូកនៃតារាងតូចនៃជួរឈរមុននិងនៅ sparse_table [i + 2 j-1 ] [ច - ​​១] ហើយទុកវាទុកអោយរាយ [i] [ច] ។
  4. ចំពោះសំណួរនីមួយៗដើម្បីដោះស្រាយយើងនៅខាងឆ្វេងនិងខាងស្តាំកំណត់តម្លៃនៃលទ្ធផលទៅ ០ ។
  5. ឆ្លងកាត់អារេពីលេខ ១៦ ដល់លេខ ០ ហើយពិនិត្យមើលថាតើនៅខាងឆ្វេង + ២j -1 តិចជាងគឺស្មើទៅនឹងសិទ្ធិបើពិត
    1. បន្ថែមតម្លៃនៃលទ្ធផលទៅ sparse_table [ខាងឆ្វេង] [j] និងទុកផលបូកចូលទៅក្នុងលទ្ធផល។
    2. ធ្វើឱ្យទាន់សម័យតម្លៃនៃខាងឆ្វេងទៅខាងឆ្វេង + 2
  6. ត្រឡប់តម្លៃនៃលទ្ធផល។

ការពន្យល់សំរាប់ Range Sum Query ដោយប្រើ Sparse Table

បានផ្តល់អារេនិងសំណួរ។ ស្វែងរកផលបូកនៃចំនួនគត់ទាំងអស់ដែលស្ថិតនៅក្នុងជួរមួយនៅក្នុងសំណួរមួយ។ យើងនឹងប្រើគំនិតតារាងរាយប៉ាយ។ យើងនឹងសាងសង់តារាងរាយប៉ាយ។ តារាងរាយប៉ាយគឺជាម៉ាទ្រីសទី ២ ដែលយើងនឹងអនុវត្តប្រតិបត្ដិការខ្លះហើយរក្សាទុកតម្លៃនៅក្នុងតារាងរាយប៉ាយ។

ប្រកាសជាលើកទី ២ ម៉ាទ្រីស។ យើងបានយកជួរមួយរយជួរនិងអតិបរមា ១៦ ជួរនីមួយៗ។ យើងបានយកលេខ ១៦ ជាពិសេសនៅទីនេះព្រោះបន្ទាប់ពីនោះយើងនឹងទទួលបានលេខដែលធំជាង ២ ដល់ស្វ័យគុណ ៥ ដូច្នេះ ១៦ គឺគ្រប់គ្រាន់ហើយ។ បន្ទាប់មកទៀតនឹងឈានដល់ដំណាក់កាលដំបូងនៃការកសាងតារាងរាយប៉ាយ។ យើងនឹងសម្គាល់ឬធ្វើបច្ចុប្បន្នភាពតម្លៃនៅលើតារាងរាយប៉ាយដែលជាធាតុអារេដែលបានផ្តល់ខណៈពេលឆ្លងកាត់អារេ។ បន្ទាប់មកដាក់ក្នុងសំបុកយើងនឹងឆ្លងកាត់អារេម្តងទៀតរហូតដល់ចំនួន k ជួរដេក។ ធ្វើបច្ចុប្បន្នភាពតារាងរាយប៉ាយនៅអាយ, ជជាផលបូកនៃតារាងរាយប៉ាយនៅអាយ, ជ - ១ និងតារាងរាយប៉ាយនៅអាយ + ២j-1, ចា -១ ។ នេះនឹងជាការធ្វើឱ្យទាន់សម័យចុងក្រោយដែលត្រូវការសម្រាប់តារាងរាយប៉ាយ។

ចំពោះសំណួរនីមួយៗដែលបានផ្តល់ឱ្យដូចជាជួរខាងស្តាំយើងត្រូវឆ្លងកាត់អារេប៉ុន្តែមុននោះកំណត់តម្លៃនៃទិន្នផលទៅ ០ ។ ប្តូរអារេពី ១៦ ដល់លេខ ០ ដូច្នេះយើងអាចទទួលបានអំនាចនៃលក្ខខណ្ឌ ២ រាល់ពេល ១ <

ការអនុវត្តន៍

កម្មវិធី C ++ សំរាប់ Range Sum Query ដោយប្រើ Sparse Table

#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

កម្មវិធីចាវ៉ាសំរាប់ Range Sum Query ដោយប្រើ Sparse Table

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” គឺជាចំនួនធាតុក្នុងអារេ។

ឯកសារយោង