დიაპაზონის ჯამის მოთხოვნა იშვიათი ცხრილის გამოყენებით


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon პუბლიკის საპიენტი 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 + 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 [left] [j] - ს დაამატეთ გამომავალი მნიშვნელობა და შეინახეთ ჯამი გამომავალში.
    2. განაახლეთ მარცხნიდან მარცხნივ +2 მნიშვნელობა
  6. დააბრუნე გამომავალი მნიშვნელობა.

დიაპაზონის ჯამის მოთხოვნის განმარტება მწირი ცხრილის გამოყენებით

მასივისა და მოთხოვნის გათვალისწინებით. გაეცანით ყველა მთელი რიცხვის ჯამს, რომელიც შედის დიაპაზონში. ჩვენ გამოვიყენებთ იშვიათი ცხრილის კონცეფციას. ჩვენ ვაშენებთ იშვიათ მაგიდას. იშვიათი ცხრილი არის 2d მატრიცა, რომელშიც ჩვენ ვაპირებთ შევასრულოთ ზოგიერთი ოპერაცია და შევინახოთ მნიშვნელობები იშვიათ ცხრილში.

გამოაცხადეთ 2d matrix. ჩვენ ავიღეთ ერთი ლარიანი რიგების ლიმიტი და მაქსიმუმ 16 სვეტი. ჩვენ აქ განსაკუთრებით მივიღეთ რიცხვი 16, რადგან ამის შემდეგ მივიღებთ რიცხვს, რომელიც 2-ზე მეტია, 5-ზე აყვანილი, ასე რომ 16 საკმარისია. შემდეგ გადავა იშვიათი მაგიდის აგების პირველ ეტაპზე. ჩვენ ვაპირებთ იშვიათი ცხრილის მნიშვნელობების აღნიშვნას ან განახლებას მასივის ელემენტის სახით მასივის გავლის დროს. შემდეგ ჩადგმული მივდივართ მასივის გადალახვაზე, ისევ k რიგამდე. განაახლეთ იშვიათი ცხრილი i- ზე, j როგორც იშვიათი ცხრილის ჯამი i- ზე, j-1 და იშვიათი მაგიდა i + 2-ზეj-1, j-1. ეს იქნება საბოლოო საჭირო განახლება იშვიათი ცხრილისთვის.

მარცხენა, მარჯვენა დიაპაზონის სახით მოცემული თითოეული მოთხოვნისთვის, ჩვენ უნდა გადავკვეთოთ მასივი, მაგრამ მანამდე დავაყენოთ გამომავალი მნიშვნელობა 0. გადავკვეთოთ მასივი 16-დან 0-მდე, ასე რომ, ჩვენ შეგვიძლია მივიღოთ სიმძლავრეები 2-ჯერ, ყოველ ჯერზე 1 <

განხორციელება

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

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 * ჟურნალი (n)) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n * ჟურნალი (n)) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

Reference