ช่วงเวลาคงที่เพิ่มการดำเนินการในอาร์เรย์


ระดับความยาก สะดวกสบาย
ถามบ่อยใน CodeNation เดอชอว์ Directi Expedia Google
แถว การเขียนโปรแกรมแบบไดนามิก

คุณได้ให้ไฟล์ จำนวนเต็ม แถว และในตอนแรกมันเริ่มต้นเป็น 0 และกำหนดช่วงด้วย งานคือการเพิ่มตัวเลขที่กำหนดในช่วงของอาร์เรย์และพิมพ์อาร์เรย์ผลลัพธ์

ตัวอย่าง

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

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

คำอธิบาย

50 ถูกเพิ่มเป็น 0 ถึง 2 ในอาร์เรย์อาร์เรย์จะกลายเป็น {50, 50, 50, 0, 0}

20 ถูกเพิ่มเป็น 3 ถึง 4 ในอาร์เรย์อาร์เรย์จะกลายเป็น {50, 50, 50, 20, 20}

30 ถูกเพิ่มเป็น 1 ถึง 3 ในอาร์เรย์อาร์เรย์จะกลายเป็น {50, 80, 80, 80, 20}

ช่วงเวลาคงที่เพิ่มการดำเนินการในอาร์เรย์

 

ขั้นตอนวิธี

  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

การใช้งานใน Java สำหรับช่วงเวลาคงที่จะเพิ่มการดำเนินการบนอาร์เรย์

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” คือจำนวนองค์ประกอบในอาร์เรย์และ "Q" คือจำนวนข้อความค้นหา เนื่องจากเราได้เพิ่มค่าที่ดัชนีด้านซ้ายและลดค่าที่ดัชนี + 1 ด้านขวาหากมีอยู่ในขอบเขตของอาร์เรย์

ความซับซ้อนของอวกาศ

บน) ที่ไหน “ N” คือจำนวนองค์ประกอบในอาร์เรย์