ຄວາມແຕກຕ່າງ Array | ການສອບຖາມປັບປຸງລະດັບໃນ O (1)


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Arcesium CodeNation Directi Expedia ກູໂກ Qualcomm
Array ບັນຫາການສອບຖາມ

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ integer array ແລະສອງປະເພດຂອງການສອບຖາມ, ໜຶ່ງ ແມ່ນເພີ່ມ ຈຳ ນວນທີ່ລະບຸໄວ້ໃນຂອບເຂດແລະອີກອັນ ໜຶ່ງ ເພື່ອພິມແຖວທັງ ໝົດ. ບັນຫາ“ Array ແຕກຕ່າງ | ການສອບຖາມປັບປຸງ Range ໃນ O (1)” ຮຽກຮ້ອງໃຫ້ພວກເຮົາ ດຳ ເນີນການປັບປຸງຊ່ວງໃນ O (1).

ຍົກຕົວຢ່າງ

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

ຄໍາອະທິບາຍ

10 ຈະຖືກເພີ່ມໃສ່ 20 ແລະ 30, ສະນັ້ນແຖວນັ້ນຈະກາຍເປັນ {30, 40, 25, 50}

ຫຼັງຈາກນັ້ນພວກເຮົາຈະພິມແຖວທັງ ໝົດ.

20 ຈະຖືກເພີ່ມໃສ່ 30, 40, ແລະ 25, ດັ່ງນັ້ນອາເລຈະກາຍເປັນ {50, 60, 45, 50}

10 ຈະຖືກເພີ່ມໃສ່ 45 ແລະ 50, ສະນັ້ນແຖວນັ້ນຈະກາຍເປັນ {50, 60, 75, 80}

ຫຼັງຈາກນັ້ນອີກເທື່ອ ໜຶ່ງ ພວກເຮົາຈະພິມແຖວທັງ ໝົດ.

ຄຸນຄ່າທັງສອງຊຸດຈະຖືກພິມອອກຫຼັງຈາກເຮັດການສອບຖາມ.

ຄວາມແຕກຕ່າງ Array | ການສອບຖາມປັບປຸງລະດັບໃນ O (1)

 

ສູດການຄິດໄລ່ ສຳ ລັບຄວາມແຕກຕ່າງ Array

  1. ສ້າງຂບວນທີ່ມີຂະ ໜາດ ດຽວກັນກັບອາເລທີ່ໃຫ້.
  2. ເລີ່ມດັດສະນີ ທຳ ອິດຕາມອົງປະກອບ ທຳ ອິດຂອງອາເລ, ແລະດັດຊະນີສຸດທ້າຍດ້ວຍ 0. ແລະຕົວຊີ້ວັດອື່ນໆແມ່ນເຕັມໄປດ້ວຍຄວາມແຕກຕ່າງຂອງອົງປະກອບປັດຈຸບັນແລະກ່ອນ ໜ້າ.
  3. ສຳ ລັບທຸກໆ ຄຳ ຖາມການປັບປຸງ, ເພີ່ມຄ່າ X ໃສ່ດັດຊະນີດ້ານຊ້າຍຂອງຕາຕະລາງທີ່ຖືກສ້າງຂື້ນມາແລະຫັກລົບ X ຈາກດັດນີຂວາຂອງຂບວນການສ້າງ.
  4. ສຳ ລັບທຸກໆ ຄຳ ຖາມທີ່ພິມ, ທຳ ອິດພວກເຮົາຕື່ມແຖວເຂົ້າໃຊ້ໂດຍໃຊ້ສູດ A [i] = D [i] + A [i-1]. ຈາກນັ້ນພິມຄ່າຕ່າງໆ.

ຄໍາອະທິບາຍ

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

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

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

ລະຫັດ

ການຈັດຕັ້ງປະຕິບັດໃນ C ++ ສຳ ລັບຄວາມແຕກຕ່າງ Array

#include<iostream>

using namespace std;

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

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

ການຈັດຕັ້ງປະຕິບັດໃນ Java ສຳ ລັບ Array ຄວາມແຕກຕ່າງ

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

ການວິເຄາະຄວາມສັບສົນ

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

ໂອ (q) ບ່ອນທີ່ "Q" ແມ່ນ ຈຳ ນວນ ຄຳ ຖາມພິມທີ່ຖືກ ດຳ ເນີນເປັນ ຄຳ ຖາມການປັບປຸງ O (1) ເວລາ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ສ້າງຂບວນການແຕກຕ່າງກັນເປັນພິເສດ, ພວກເຮົາມີຄວາມສັບສົນໃນພື້ນທີ່ເສັ້ນ.