เทคนิคการสลายตัว Sqrt (หรือรากที่สอง)


ระดับความยาก ยาก
ถามบ่อยใน จังหวะอินเดีย บัตรเครดิต/เดบิต หรือ PayPal Qualtrics Roblox Twilio
แถว ปัญหาการสืบค้น

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

อัปเดต: (ดัชนีค่า) ถูกกำหนดเป็นแบบสอบถามซึ่งคุณต้องอัปเดตค่าของอาร์เรย์ที่ดัชนีตำแหน่งด้วย 'value'

ผลรวม: (ซ้าย, ขวา) ได้รับการสืบค้น, สรุปตัวเลขทั้งหมดที่มาในช่วง

ตัวอย่าง

อินพุต

arr [] = {2,4,7,1,5,8,9,10,3,6}

แบบสอบถามผลรวม (0, 3)

แบบสอบถามผลรวม (4, 9)

ปรับปรุง (5, 8)

แบบสอบถามผลรวม (3, 7)

เอาท์พุต

14 ผลรวมของตัวเลขภายในช่วง 0 และ 3 คือ 14 (2 + 4 + 7 + 1)

41 ผลรวมของตัวเลขภายในช่วง 4 และ 9 คือ 41 (5 + 8 + 9 + 10 + 3 + 6)

การอัปเดตค่าที่อาร์เรย์ [5] เป็น 8

33 ผลรวมของตัวเลขภายในช่วง 0 และ 3 คือ 14 (1 + 5 + 8 + 9 + 10)

ขั้นตอนวิธี

  1. รับค่ารากที่สองของ n เป็นขนาดบล็อกและข้ามอาร์เรย์
  2. คัดลอกค่าของอาร์เรย์อินพุตไปยังอาร์เรย์ที่เราสร้างขึ้นและตรวจสอบว่าดัชนีใดหารด้วยบล็อกขนาดได้หรือไม่หากเพิ่มค่าของ blockindex ขึ้น 1 และเพิ่มค่าของ arr [i] ให้กับ blockArray ที่ blockindex
  3. หากต้องการสรุปมูลค่าในช่วงที่กำหนดให้ตั้งค่าผลรวมเป็น 0
  4. ทำตามสามขณะลูปจนกว่าด้านซ้ายจะน้อยกว่าค่าของด้านขวาซ้ายไม่ควรเป็นศูนย์และด้านซ้ายไม่ควรเป็นกรณีมุมของบล็อกใด ๆ จากนั้นเพิ่มค่าอาร์เรย์ [ซ้าย] ลงในผลรวมและเพิ่มค่า มูลค่าด้านซ้าย
  5. ในสิ่งนี้ขนาดบล็อกด้านซ้ายบวกควรน้อยกว่าด้านขวาจากนั้นเพิ่มค่าของ blockArray ที่ดัชนีเป็นส่วนของด้านซ้ายและขนาดบล็อกและเพิ่มค่าของขนาดบล็อกทางด้านซ้าย
  6. ในสิ่งนี้ด้านซ้ายจะน้อยกว่าด้านขวาเพิ่มค่าของอาร์เรย์ [ซ้าย] ให้กับผลรวมและเพิ่มค่าของด้านซ้าย 1 และส่งกลับค่าของผลรวม
  7. สำหรับแบบสอบถามการอัปเดตใด ๆ ให้รับการแบ่งดัชนีและบล็อกขนาดและเพิ่มค่าที่กำหนดให้อัปเดตและลบอาร์เรย์ [ดัชนี] ในการอัปเดต 'ค่า' ที่อาร์เรย์ [ดัชนี] ครั้งล่าสุด

คำอธิบาย

การสลายตัวของรากที่สองเป็นเทคนิคในการแก้คำถามเพื่อลดความซับซ้อนในรูปของรากที่สองของ sqrt (n) กำหนดอาร์เรย์และช่วงเคียวรีเพื่อค้นหาผลรวมของตัวเลขทั้งหมดที่อยู่ในช่วงที่กำหนดของแต่ละคิวรีและอีกภารกิจหนึ่งคือการอัปเดตค่าที่ดัชนีที่กำหนด ดังนั้นเราจึงได้รับคำถามบางอย่างและเราจำเป็นต้องแก้ปัญหานั้นเราสามารถแก้ได้โดยใช้วิธีไร้เดียงสา ในแนวทางนั้นเราจะแก้ปัญหาโดยการวนซ้ำแต่ละองค์ประกอบในอาร์เรย์ภายในช่วงที่กำหนดของซ้ายและขวาและรวมค่าทั้งหมดที่มีอยู่ในช่วง แต่ที่นี่สำหรับความซับซ้อนของเวลาเข้าใกล้สำหรับแต่ละวิธีจะเป็น O (n) .

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

สมมติว่าเรามี sqrt (16) บล็อกตั้งแต่ 16 เป็นกำลังสองสมบูรณ์ เราจะมี 4 บล็อกและแต่ละบล็อกจะมี 4 องค์ประกอบ แต่ละบล็อกเราจะมีผลรวมขององค์ประกอบทั้งหมดที่อยู่ในแต่ละบล็อก ดังนั้นหากเราขอให้หาผลรวมของการสืบค้นช่วงใด ๆ เราสามารถหาผลรวมได้อย่างง่ายดายโดยใช้ผลรวมบล็อก

การใช้งานใน C ++ สำหรับเทคนิคการสลายตัวของ Sqrt (หรือสแควร์รูท)

#include<iostream>
#include<math.h>

using namespace std;


int arr[10000];
int blockArray[100];
int blockSize;

void buildArray(int input[], int n)
{
    int blockIndex = -1;

    blockSize = sqrt(n);

    for (int i=0; i<n; i++)
    {
        arr[i] = input[i];
        if (i%blockSize == 0)
        {
            blockIndex++;
        }
        blockArray[blockIndex] += arr[i];
    }
}

void update(int index, int value)
{
    int blockNumber = index / blockSize;
    blockArray[blockNumber] += value - arr[index];
    arr[index] = value;
}

int solveQuery(int left, int right)
{
    int sum = 0;
    while (left<right and left%blockSize!=0 and left!=0)
    {
        sum += arr[left];
        left++;
    }
    while (left+blockSize <= right)
    {
        sum += blockArray[left/blockSize];
        left += blockSize;
    }
    while (left<=right)
    {
        sum += arr[left];
        left++;
    }
    return sum;
}

int main()
{
    int inputArray[] = {2,4,7,1,5,8,9,10,3,6};
    int n = sizeof(inputArray)/sizeof(inputArray[0]);

    buildArray(inputArray, n);

    cout << "first Query : " << solveQuery(0, 3) << endl;
    cout << "second Query : " << solveQuery(4, 9) << endl;
    update(5, 8);
    cout << "third Query : " << solveQuery(3, 7) << endl;
    return 0;
}
first Query : 14
second Query : 41
third Query : 33

การใช้งานใน Java สำหรับเทคนิคการสลายตัวของ Sqrt (หรือ Square Root)

class SquareRootDecomposition
{

    static int []arr = new int[10000];
    static int []blockArray = new int[100];
    static int blockSize;

    static void buildArray(int input[], int n)
    {
        int blockIndex = -1;

        blockSize = (int) Math.sqrt(n);

        for (int i = 0; i < n; i++)
        {
            arr[i] = input[i];
            if (i % blockSize == 0)
            {
                blockIndex++;
            }
            blockArray[blockIndex] += arr[i];
        }
    }

    static void update(int idx, int val)
    {
        int blockNumber = idx / blockSize;
        blockArray[blockNumber] += val - arr[idx];
        arr[idx] = val;
    }

    static int solveQuery(int left, int right)
    {
        int sum = 0;
        while (left<right && left%blockSize!=0 && left!=0)
        {
            sum += arr[left];
            left++;
        }
        while (left+blockSize <= right)
        {
            sum += blockArray[left/blockSize];
            left += blockSize;
        }
        while (left<=right)
        {
            sum += arr[left];
            left++;
        }
        return sum;
    }

    public static void main(String[] args)
    {
        int input[] = {2,4,7,1,5,8,9,10,3,6};
        int n = input.length;

        buildArray(input, n);

        System.out.println("first Query: " + solveQuery(0, 3));
        System.out.println("second Query : " + solveQuery(4, 9));
        update(5, 8);
        System.out.println("third Query : " + solveQuery(3, 7));
    }
}
first Query: 14
second Query : 41
third Query : 33

การวิเคราะห์ความซับซ้อนสำหรับเทคนิคการสลายตัวของ Sqrt (หรือรากที่สอง)

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

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

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

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