ຊ່ວງເວລາຄົງທີ່ເພີ່ມການ ດຳ ເນີນງານໃນອາເລ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ລະຫັດປະເທດ DE Shaw Directi Expedia ກູໂກ
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ທ່ານໄດ້ໃຫ້ integer array ແລະໃນເບື້ອງຕົ້ນ, ມັນໄດ້ຖືກເລີ່ມຕົ້ນເປັນ 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}

ຊ່ວງເວລາຄົງທີ່ເພີ່ມການ ດຳ ເນີນງານໃນອາເລPin

 

ລະບົບວິເຄາະ  

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

ຄຳ ອະທິບາຍ ສຳ ລັບຊ່ວງເວລາທີ່ ຈຳ ກັດເພີ່ມການ ດຳ ເນີນງານໃນອາເລ  

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

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

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

ເບິ່ງ
ການແຊກຊືມຂັ້ນຕ່ ຳ ເພື່ອປະກອບ palindrome ທີ່ມີການອະນຸຍາດ

ລະຫັດ  

ການຈັດຕັ້ງປະຕິບັດໃນ 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" ແມ່ນຈໍານວນຂອງອົງປະກອບໃນຂບວນການແລະ "ຖາມ" ແມ່ນ ຈຳ ນວນ ຄຳ ຖາມ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ເພີ່ມມູນຄ່າຢູ່ໃນດັດຊະນີເບື້ອງຊ້າຍແລະຫຼຸດລົງມູນຄ່າທີ່ຢູ່ໃນດັດຊະນີ + 1 ຂວາຖ້າມັນມີຢູ່ໃນເຂດແດນຂອງອາເລ.

ເບິ່ງ
K ລວມຍອດຍ່ອຍສູງສຸດຂອງອາຄານຍ່ອຍຕິດກັນທີ່ຕິດກັນ

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

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