ជួរពេលវេលាថេរបន្ថែមប្រតិបត្តិការលើអារេមួយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ លេខកូដ DE Shaw Directi Expedia ក្រុមហ៊ុន google
អារេ ការសរសេរកម្មវិធីឌីណាមិក

អ្នកបានផ្តល់ឱ្យ integer អារេ ហើយដំបូងវាត្រូវបានចាប់ផ្តើមជាលេខ ០ ហើយវាក៏បានផ្តល់ជាជួរផងដែរ។ ភារកិច្ចគឺត្រូវបន្ថែមលេខដែលបានផ្តល់ឱ្យនៅក្នុងជួរនៃអារេហើយបោះពុម្ពអារេលទ្ធផល។

ឧទាហរណ៍

arr[] = {0, 0, 0, 0, 0}

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

ការពន្យល់

50 ត្រូវបានបន្ថែមទៅ 0 ទៅ 2 នៅក្នុងជួរអារេនឹងក្លាយជា {៥០, ៥០, ៥០, ០, ០}

20 ត្រូវបានបន្ថែមទៅ 3 ទៅ 4 នៅក្នុងជួរអារេនឹងក្លាយជា {៥០, ៥០, ៥០, ០, ០}

30 ត្រូវបានបន្ថែមទៅ 1 ទៅ 3 នៅក្នុងជួរអារេនឹងក្លាយជា {៥០, ៥០, ៥០, ០, ០}

ជួរពេលវេលាថេរបន្ថែមប្រតិបត្តិការលើអារេមួយ

 

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

  1. សម្រាប់សំណួរនីមួយៗនៃជួរអនុវត្តតាមជំហាន។
    1. បន្ថែមតម្លៃដែលបានផ្តល់នៅសន្ទស្សន៍ខាងឆ្វេងនៃអារេហើយរក្សាទុកវាដោយខ្លួនឯង។
    2. ពិនិត្យមើលថាតើតម្លៃខាងស្តាំមិនស្មើនឹងសន្ទស្សន៍អារេចុងក្រោយទេបន្ទាប់មកដកតម្លៃដែលបានផ្តល់ឱ្យនៅទីតាំងខាងស្តាំ + 1 នៃអារេហើយរក្សាទុកវាដោយខ្លួនឯង។
  2. មុនពេលបោះពុម្ពអារេធ្វើបច្ចុប្បន្នភាពអារេដូចឆ្លងកាត់អារេហើយបន្ថែមតម្លៃមុននិងបច្ចុប្បន្នហើយរក្សាទុកវាទៅតម្លៃអារេដោយខ្លួនឯង។
  3. បន្ទាប់ពីការធ្វើបច្ចុប្បន្នភាពសូមបោះពុម្ពអារេលទ្ធផល។

ការពន្យល់អំពីជួរពេលវេលាថេរបន្ថែមប្រតិបត្តិការលើអារេមួយ

បានផ្តល់អារេចំនួនគត់និងចំនួនត្រូវបន្ថែម។ យើងក៏ត្រូវបានផ្តល់ជួរនៃសំណួរ។ វាមានចំណុចចាប់ផ្តើមនៃជួរខាងឆ្វេងនិងចំណុចបញ្ចប់នៃជួរខាងស្ដាំ។ យើងត្រូវបានស្នើសុំឱ្យបន្ថែមលេខដែលបានផ្តល់ឱ្យនៅក្នុងជួរដែលបានផ្តល់ឱ្យទៅចំនួនគត់ដែលអាចធ្វើបាន។ ហើយទីបំផុតបោះពុម្ពអារេលទ្ធផល។ សម្រាប់បញ្ហានេះយើងនឹងអនុវត្តប្រតិបត្តិការបន្ថែមតាមរបៀបដែលត្រូវបានកែប្រែ។ យើងនឹងបំពេញតម្លៃសន្ទស្សន៍អារេជាមួយនឹងតម្លៃដែលបានផ្តល់នៅទីតាំងខាងឆ្វេងនិងស្តាំ + 1 នៃអារេនិងមុនពេលបោះពុម្ពការធ្វើបច្ចុប្បន្នភាពអារេនោះ។

ចំពោះសំណួរដែលបានផ្តល់នីមួយៗខាងឆ្វេងនិងខាងស្តាំយើងនឹងបន្ថែមតម្លៃដែលបានផ្តល់ឱ្យនៅសន្ទស្សន៍ខាងឆ្វេងនៃខាងស្តាំសូមចងចាំតែនៅសន្ទស្សន៍ខាងឆ្វេង។ ហើយចំពោះតម្លៃត្រឹមត្រូវយើងនឹងពិនិត្យមើលថាតើតម្លៃខាងស្តាំមិនស្មើនឹងសន្ទស្សន៍ចុងក្រោយនៃអារេប្រសិនបើលក្ខខណ្ឌដែលបានផ្តល់ឱ្យពេញចិត្តនោះយើងនឹងធ្វើបច្ចុប្បន្នភាពសន្ទស្សន៍តម្លៃដែលបានផ្តល់ឱ្យយើងនឹងដកតម្លៃដែលបានផ្តល់ពី សន្ទស្សន៍ខាងស្តាំនៃអារេហើយរក្សាទុកវាទៅសន្ទស្សន៍ទីតាំងខាងស្តាំនៃអារេខ្លួនឯង។ សម្រាប់សំណួរនីមួយៗយើងនឹងអនុវត្តប្រតិបត្តិការទាំងនេះ។

ឥឡូវយើងត្រូវបោះពុម្ពអារេប៉ុន្តែមុននោះយើងនឹងធ្វើបច្ចុប្បន្នភាពតម្លៃទាំងអស់ប្រតិបត្តិការបន្ថែមដែលយើងបានអនុវត្តយើងត្រូវធ្វើបច្ចុប្បន្នភាព។ ដូច្នេះធ្វើឱ្យទាន់សម័យអារេដោយឆ្លងកាត់អារេនិងបន្ថែមតម្លៃបច្ចុប្បន្ននិងតម្លៃមុននៃអារេដែលបានផ្តល់ហើយរក្សាទុកវាទៅទីតាំងបច្ចុប្បន្ននៃអារេ។ បន្ទាប់មកយើងនឹងបោះពុម្ពអារេ។

លេខកូដ

ការអនុវត្តនៅក្នុង C ++ សម្រាប់ជួរពេលវេលាថេរបន្ថែមប្រតិបត្តិការលើអារេមួយ

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

ការអនុវត្តនៅក្នុងចាវ៉ាសម្រាប់ចន្លោះពេលថេរបន្ថែមប្រតិបត្តិការលើអារេមួយ

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N + Q) ដែលជាកន្លែងដែល “ N” គឺជាចំនួនធាតុក្នុងអារេនិង "សំណួរ" គឺជាចំនួនសំណួរ។ ពីព្រោះយើងបានបង្កើនតម្លៃនៅសន្ទស្សន៍ខាងឆ្វេងនិងបន្ថយតម្លៃនៅសន្ទស្សន៍ខាងស្តាំ + ១ ប្រសិនបើវាមាននៅក្នុងព្រំដែននៃអារេ។

ភាពស្មុគស្មាញនៃលំហ

O (N) ដែលជាកន្លែងដែល “ N” គឺជាចំនួនធាតុក្នុងអារេ។