แบบสอบถามผลรวมช่วงที่ไม่มีการอัปเดต


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แบล็ค GE Healthcare Moonfrog Labs Synopsys Taxi4Sure Twilio
แถว เสน & Toubro ปัญหาการสืบค้น

คำชี้แจงปัญหา

ปัญหา“ การสืบค้นผลรวมช่วงที่ไม่มีการอัปเดต” ระบุว่าคุณมีไฟล์ แถว of จำนวนเต็ม และช่วง คำสั่งปัญหาจะขอให้ค้นหาผลรวมขององค์ประกอบทั้งหมดภายในช่วงที่กำหนด

ตัวอย่าง

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

คำอธิบาย

ผลรวมของตัวเลขทั้งหมดระหว่างช่วง (0, 4) รวมเป็น 40 และผลรวมของตัวเลขทั้งหมดระหว่างช่วง (1, 3) รวมเป็น 24

แบบสอบถามผลรวมช่วงที่ไม่มีการอัปเดต

 

ขั้นตอนวิธี

  1. สร้างอาร์เรย์ sumArray ที่มีขนาดเท่ากับอาร์เรย์ที่กำหนด
  2. สำรวจผ่านอาร์เรย์ที่กำหนดและเก็บผลรวมขององค์ประกอบก่อนหน้าของ sumArray และองค์ประกอบปัจจุบันของอาร์เรย์ที่กำหนดและเก็บไว้ใน sumArray
  3. สำหรับแต่ละแบบสอบถามถ้าทางซ้ายเท่ากับ 0 ให้ส่งคืน sumArray [ขวา]
  4. อื่นส่งคืน sumArray [ขวา] - sumArray [ซ้าย - 1]

คำอธิบาย

เราได้ให้อาร์เรย์ของจำนวนเต็มและช่วงเราถูกขอให้ค้นหาผลรวมขององค์ประกอบทั้งหมดภายในช่วงที่กำหนดสำหรับแต่ละข้อความค้นหา แต่ละคำค้นหาประกอบด้วยช่วงเป็นจุดเริ่มต้นและจุดสิ้นสุดของช่วง คำถามนี้ไม่เกี่ยวข้องกับการสอบถามการอัปเดตใด ๆ นั่นหมายความว่าไม่จำเป็นต้องอัปเดตสิ่งใด ๆ ในขณะที่ค้นหาคำตอบของแบบสอบถาม เราจะสร้างอาร์เรย์ที่กำหนดเพื่อให้ผลรวมขององค์ประกอบทั้งหมดจากดัชนี 0 ถึงดัชนีปัจจุบันอยู่ที่ตำแหน่ง ith ของอาร์เรย์ที่สร้างขึ้น ด้วยวิธีนี้ทุกแบบสอบถามจะได้รับการแก้ไขใน O (1) โดยมีช่องว่างพิเศษ O (n)

เราจะสร้าง sumArray ที่เราสร้างขึ้น ใน sumArray นี้ผลรวมขององค์ประกอบตั้งแต่ 0 ถึง i จะถูกเก็บไว้ที่ตำแหน่ง ith ของ sumArray เราจะคำนวณสิ่งนี้เมื่อเราบวกค่าก่อนหน้าของ sumArray และค่าปัจจุบันของอาร์เรย์ที่กำหนดและเก็บไว้ในตำแหน่งดัชนีปัจจุบันของ sumArray ในขณะที่ข้าม ดังนั้นเมื่อมีคนถามว่าผลรวมของตัวเลขทั้งหมดในตำแหน่งนี้เป็นเท่าใดเราก็ต้องคืนค่าของตำแหน่งนั้นสำหรับองค์ประกอบอาร์เรย์ที่ไม่ซ้ำกันทุกรายการ

เมื่อเราจะได้รับข้อความค้นหาที่ประกอบด้วยช่วงใด ๆ และหากเราพบว่าจุดเริ่มต้นทางซ้ายหรือจุดเริ่มต้นของช่วงนั้นมีค่าเท่ากับ 0 เราจะส่งคืนค่าของ sumArray [ขวา] ตามที่กล่าวไว้ข้างต้นคือช่วงทางซ้าย ไม่เท่ากับ 0 เราจะคืนค่าความแตกต่างของ sumArray [ขวา] และ sumArray [ซ้าย-1] สิ่งเหล่านี้จะเป็นคำตอบที่จำเป็น วิธีนี้ยังเป็นวิธีที่ง่ายที่สุดอีกวิธีหนึ่งที่เราใช้ การเขียนโปรแกรมแบบไดนามิก.

รหัส

รหัส C ++ สำหรับการสืบค้นผลรวมช่วงที่ไม่มีการอัปเดต

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

โค้ด Java สำหรับการสืบค้น Range sum โดยไม่มีการอัพเดต

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (N + Q),  เนื่องจากเราต้องการ O (N) ในการคำนวณ sumArray และเวลา O (1) สำหรับแต่ละแบบสอบถาม

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

ในแนวทางที่กำหนดเราได้สร้าง sumArray อาร์เรย์ใหม่เพื่อเก็บผลรวมขององค์ประกอบตั้งแต่ 0 ถึง i ดังนั้นจึงต้องใช้แนวทางนี้ บน) พื้นที่. แต่เราสามารถแก้ไขอาร์เรย์เดิมได้ด้วย จากนั้นความซับซ้อนของอวกาศจะลดลงจนคงที่