Sqrt (ຫລືຮາກຮາກ) ເຕັກນິກການເນົ່າເປື່ອຍ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Cadence ອິນເດຍ PayPal Qualtrics ຟລີໂຄ້ດ Twilio
Array ບັນຫາການສອບຖາມ

ທ່ານໄດ້ຮັບການສອບຖາມກ່ຽວກັບຂອບເຂດຂອງເລກເຕັມ array. ທ່ານຈະຖືກຮ້ອງຂໍໃຫ້ ກຳ ນົດຜົນລວມຂອງ ຈຳ ນວນທັງ ໝົດ ທີ່ມາໃນຂອບເຂດຂອງ ຄຳ ຖາມທີ່ໃຫ້. ການສອບຖາມແມ່ນສອງປະເພດ, ນັ້ນແມ່ນ -

ການປັບປຸງ: (ດັດສະນີ, ມູນຄ່າ) ແມ່ນໃຫ້ເປັນແບບສອບຖາມ, ບ່ອນທີ່ທ່ານຕ້ອງການປັບປຸງມູນຄ່າຂອງອາເລທີ່ດັດສະນີ ຕຳ ແໜ່ງ ກັບ 'ຄ່າ'.

ສະຫຼຸບ: (ຊ້າຍ, ຂວາ) ແມ່ນໃຫ້ການສອບຖາມ, ສັງລວມຕົວເລກທັງ ໝົດ ທີ່ເຂົ້າມາໃນຂອບເຂດ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ

ຮອດ [] = {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)

ການປັບປຸງມູນຄ່າທີ່ array [5] ເປັນ 8.

33 ຜົນລວມຂອງຕົວເລກພາຍໃນຂອບເຂດ 0 ແລະ 3, ແມ່ນ 14 (1 + 5 + 8 + 9 + 10)

ລະບົບວິເຄາະ

  1. ໄດ້ຮັບຄ່າຮາກຮຽບຮ້ອຍຂອງ n ເປັນ blockize ແລະຂ້າມອາເລ.
  2. ຄັດລອກຄ່າຂອງການປ້ອນຂໍ້ມູນເຂົ້າໃນອາເລທີ່ພວກເຮົາສ້າງຂື້ນມາແລະກວດເບິ່ງວ່າມີດັດສະນີໃດ ໜຶ່ງ ທີ່ສາມາດແບ່ງແຍກໄດ້ໂດຍ blockize ຖ້າມັນເພີ່ມມູນຄ່າຂອງ blockindex ໂດຍ 1 ແລະເພີ່ມມູນຄ່າຂອງ arr [i] ໃສ່ blockArray ທີ່ blockindex.
  3. ເພື່ອສະຫຼຸບມູນຄ່າໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້, ໃຫ້ ກຳ ນົດຄ່າຂອງຜົນບວກກັບ 0.
  4. ປະຕິບັດຕາມສາມໃນຂະນະທີ່ loops, ຈົນກ່ວາເບື້ອງຊ້າຍແມ່ນຫນ້ອຍກ່ວາມູນຄ່າຂອງສິດ, ຊ້າຍບໍ່ຄວນຈະເປັນສູນແລະຊ້າຍບໍ່ຄວນຈະເປັນກໍລະນີທີ່ແຈຂອງທ່ອນໄມ້ໃດໆ, ຫຼັງຈາກນັ້ນຕື່ມມູນຄ່າຂອງອາເລ [ຊ້າຍ] ໃສ່ຜົນລວມແລະເພີ່ມຄ່າ ມູນຄ່າຂອງຊ້າຍ.
  5. ໃນນີ້, ບລັອກບວກເບື້ອງຊ້າຍຄວນຈະ ໜ້ອຍ ກວ່າເບື້ອງຂວາ, ຫຼັງຈາກນັ້ນເພີ່ມມູນຄ່າຂອງ blockArray ຢູ່ທີ່ດັດຊະນີຄືການແບ່ງສ່ວນເບື້ອງຊ້າຍແລະຕັນ, ແລະເພີ່ມມູນຄ່າຂອງ blockize ຢູ່ເບື້ອງຊ້າຍ.
  6. ໃນນີ້, ເບື້ອງຊ້າຍແມ່ນນ້ອຍກວ່າດ້ານຂວາ, ເພີ່ມຄ່າຂອງອາເລ [ຊ້າຍ] ໃສ່ຜົນລວມແລະເພີ່ມຄ່າຂອງເບື້ອງຊ້າຍ 1, ແລະສົ່ງຄືນຄ່າຂອງຜົນລວມ.
  7. ສຳ ລັບ ຄຳ ຖາມການປັບປຸງໃດ ໜຶ່ງ, ໃຫ້ແບ່ງສ່ວນດັດສະນີແລະປິດ, ແລະເພີ່ມມູນຄ່າທີ່ໄດ້ຖືກປັບປຸງແລະຫັກລົບອາເລ [ດັດສະນີ]. ໃນການປັບປຸງຄັ້ງສຸດທ້າຍ 'ມູນຄ່າ' ທີ່ array [ດັດສະນີ].

ຄໍາອະທິບາຍ

ການເນົ່າເປື່ອຍຮາກຮຽບຮ້ອຍແມ່ນເຕັກນິກໃນການແກ້ໄຂ ຄຳ ຖາມເພື່ອຫຼຸດຜ່ອນຄວາມສັບສົນໃນແງ່ຂອງຮາກມົນທົນຂອງ sqrt (n). ມີແຖວແລະຂອບເຂດການສອບຖາມເພື່ອຊອກຫາຜົນລວມຂອງຕົວເລກທັງ ໝົດ ທີ່ຢູ່ໃນຂອບເຂດທີ່ລະບຸໄວ້ໃນແຕ່ລະ ຄຳ ຖາມແລະ ໜ້າ ວຽກອີກອັນ ໜຶ່ງ ແມ່ນການປັບປຸງມູນຄ່າຢູ່ໃນດັດຊະນີທີ່ໃຫ້ໄວ້. ດັ່ງນັ້ນໃນນີ້ພວກເຮົາໄດ້ຮັບການສອບຖາມບາງຢ່າງ, ແລະພວກເຮົາຕ້ອງການແກ້ໄຂບັນຫານັ້ນ, ພວກເຮົາສາມາດແກ້ໄຂໄດ້ໂດຍໃຊ້ວິທີການທີ່ບໍ່ມີຕົວຕົນ. ໃນວິທີການນັ້ນພວກເຮົາຈະແກ້ໄຂດ້ວຍການແກ້ໄຂແຕ່ລະອົງປະກອບໃນອາເລພາຍໃນຂອບແລະຊ້າຍແລະລວມທັງ ໝົດ ຂອງຄ່າທີ່ມີຢູ່ໃນຂອບເຂດ, ແຕ່ໃນທີ່ນີ້ ສຳ ລັບວິທີການນີ້ເວລາສັບສົນ ສຳ ລັບແຕ່ລະວິທີຈະເປັນ O (n) .

ສະນັ້ນເພື່ອເພີ່ມປະສິດທິພາບການສອບຖາມໃຫ້ມີປະສິດທິພາບສູງສຸດ, ພວກເຮົາຈະ ນຳ ໃຊ້ການເນົ່າເປື່ອຍຮາກ, ຊ່ວຍພວກເຮົາຫຼຸດຜ່ອນຄວາມສັບສົນໃນເວລາ. ພວກເຮົາສາມາດສົມມຸດວ່າແຖວຂະ ໜາດ n ປະກອບດ້ວຍອົງປະກອບ n. ພວກເຮົາຈະແບ່ງອາເລນເປັນທ່ອນນ້ອຍໆຫລືທ່ອນໄມ້ຂະ ໜາດ sqrt (n). ສຳ ລັບທຸກໆຕາລາງທີ່ສົມບູນແບບເປັນ ຈຳ ນວນ ໜຶ່ງ, ພວກເຮົາຈະມີທ່ອນ sqrt ທີ່ຖືກຕ້ອງ. ດ້ວຍການເນົ່າເປື່ອຍຂອງອາເລນີ້, ພວກເຮົາຈະມີຕັນ sqrt (n) ແລະໃນແຕ່ລະທ່ອນໄມ້. ພວກເຮົາຈະມີອົງປະກອບ sqrt (n) ຖ້າ n ແມ່ນຮູບສີ່ຫລ່ຽມທີ່ສົມບູນແບບ, ບ່ອນທີ່ n ແມ່ນຂະ ໜາດ ຂອງອາເລ.

ສົມມຸດວ່າພວກເຮົາມີຕັນ sqrt (16) ຕັ້ງແຕ່ 16 ແມ່ນຮຽບຮ້ອຍທີ່ສົມບູນແບບ. ພວກເຮົາຈະມີ 4 ທ່ອນໄມ້ຢ່າງແນ່ນອນແລະແຕ່ລະທ່ອນຈະປະກອບມີ 4 ສ່ວນປະກອບຢ່າງແນ່ນອນ. ແຕ່ລະທ່ອນໄມ້ພວກເຮົາຈະມີຜົນລວມຂອງສ່ວນປະກອບທັງ ໝົດ ທີ່ນອນຢູ່ໃນແຕ່ລະ block. ສະນັ້ນຖ້າພວກເຮົາຮ້ອງຂໍໃຫ້ຊອກຫາຜົນລວມຂອງການສອບຖາມຊ່ວງໃດ ໜຶ່ງ. ພວກເຮົາສາມາດຊອກຫາຍອດລວມໄດ້ຢ່າງງ່າຍດາຍໂດຍການໃຊ້ block sum.

ການປະຕິບັດໃນ 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 (ຫລືຮາກຮາກ)

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບເຕັກນິກການເຊື່ອມໂຊມ (ຫຼືຮາກຮາກ)

ຄວາມສັບສົນເວລາ

O (sqrt (n)) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ຄວາມສັບສົນໃນອະວະກາດ

O (sqrt (n)) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.