ຈຳ ນວນຂອງອົງປະກອບນ້ອຍກວ່າຫຼືເທົ່າກັບ ຈຳ ນວນທີ່ໃຫ້ໄວ້ໃນ subarray ທີ່ໃຫ້


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ CodeNation DE Shaw ກູໂກ Opera PayPal Pinterest
Array ຕົ້ນໄມ້

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ ຈຳ ນວນຂອງອົງປະກອບທີ່ນ້ອຍກວ່າຫລືເທົ່າກັບຕົວເລກທີ່ລະບຸໃນ subarray ທີ່ລະບຸໄວ້” ລະບຸວ່າທ່ານໄດ້ຖືກມອບໃຫ້ເປັນ array integer ແລະ q number ຂອງການສອບຖາມ. ຈະມີສອງແບບສອບຖາມà

  • queryUpdate (i, v): ມັນຈະມີສອງຕົວເລກ i ແລະ v, ເຊັ່ນວ່າການປັບປຸງອາເລ [i] = v.
  • queryPrint (ຊ້າຍ, ຂວາ, k): ພິມ ຈຳ ນວນເລກເຕັມພາຍໃນຂອບເຂດທີ່ນ້ອຍກວ່າ k.

ຍົກຕົວຢ່າງ

arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)
1 2 1

ຄໍາອະທິບາຍ

queryPrint (0, 2, 2) ຈະພິມ ຈຳ ນວນຂອງອົງປະກອບນ້ອຍກວ່າຫລືເທົ່າກັບ 2 ຈາກດັດຊະນີ 0 ເຖິງ 2 ເຊັ່ນ, 1

queryUpdate (2, 8) ຈະປັບປຸງອົງປະກອບທີ່ດັດສະນີ 2 ດ້ວຍຄ່າ 8 ເຊັ່ນ, ມາຮອດຈະເປັນ {2, 4, 8, 1, 5}

queryPrint (1, 3, 5) ຈະພິມ ຈຳ ນວນຂອງອົງປະກອບນ້ອຍກວ່າຫລືເທົ່າກັບ 5 ຈາກດັດຊະນີ 1 ເຖິງ 3 ເຊັ່ນ, 2

queryUpdate (4, 3) ຈະປັບປຸງອົງປະກອບທີ່ດັດສະນີ 4 ດ້ວຍ 3 ຕົວຢ່າງ, ມາຮອດຈະເປັນ {2, 4, 8, 1, 3}

queryUpdate (1, 3) ຈະປັບປຸງອົງປະກອບທີ່ດັດສະນີ 1 ດ້ວຍ 3 ຕົວຢ່າງ, ມາຮອດຈະເປັນ {2, 3, 8, 1, 3}

queryPrint (1, 2, 4) ຈະພິມ ຈຳ ນວນຂອງອົງປະກອບນ້ອຍກວ່າຫລືເທົ່າກັບ 4 ຈາກດັດຊະນີ 1 ເຖິງ 2 ເຊັ່ນ, 1

ຈຳ ນວນຂອງອົງປະກອບນ້ອຍກວ່າຫຼືເທົ່າກັບ ຈຳ ນວນທີ່ໃຫ້ໄວ້ໃນ subarray ທີ່ໃຫ້

 

ສູດການຄິດໄລ່ ສຳ ລັບການຊອກຫາຕົວເລກ <= ໃຫ້ມູນຄ່າໃນ subarray

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

ຄໍາອະທິບາຍ

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

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

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

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຊອກຫາຕົວເລກ <= ໃຫ້ມູນຄ່າໃນ subarray

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

using namespace std;

const int MAX = 10001;

void update(int index, int block, int val, int bit[][MAX])
{
    for (; index < MAX ; index += (index&-index))
        bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
    int sum = 0;
    while (left<right && left%blockSize!=0 && left!=0)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }

    while (left + blockSize <= right)
    {
        int index = k;
        for (; index > 0 ; index -= index&-index)
            sum += bit[left/blockSize][index];
        left += blockSize;
    }

    while (left <= right)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }
    return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
    for (int i=0; i<n; i++)
        update(arr[i], i/blockSize, 1, bit);
}

void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
    update(arr[i], i/blockSize, -1, bit);
    update(v, i/blockSize, 1, bit);
    arr[i] = v;
}
int main()
{
    int arr[] = {2,4,6,1,5};
    int n = sizeof(arr)/sizeof(arr[0]);

    int blockSize = sqrt(n);

    int bit[blockSize+1][MAX];

    memset(bit, 0, sizeof(bit));

    preprocess(arr, blockSize, n, bit);

    cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;

    queryUpdate(2, 8, blockSize, arr, bit);

    cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;

    queryUpdate(4, 3, blockSize, arr, bit);

    queryUpdate(1, 3, blockSize, arr, bit);

    cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
    return 0;
}
1
2
1

ລະຫັດ Java ສຳ ລັບການຊອກຫາຕົວເລກ <= ມີມູນຄ່າໃນ subarray

class NumberElements
{
    static final int MAX = 10001;

    static void update(int index, int block, int val, int bit[][])
    {
        for ( ; index < MAX ; index += (index&-index))
            bit[block][index] += val;
    }
    static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
    {
        int sum = 0;
        while (left < right && left % blockSize != 0 && left != 0)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        while (left + blockSize <= right)
        {
            int index = k;
            for (; index > 0 ; index -= index&-index)
                sum += bit[left/blockSize][index];
            left += blockSize;
        }
        while (left <= right)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        return sum;
    }
    static void buildArray(int arr[], int blockSize, int n, int bit[][])
    {
        for (int i=0; i<n; i++)
            update(arr[i], i/blockSize, 1, bit);
    }

    static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
    {
        update(arr[i], i/blockSize, -1, bit);
        update(v, i/blockSize, 1, bit);
        arr[i] = v;
    }

    public static void main(String args[])
    {
        int arr[] = {2,4,6,1,5};

        int blockSize = (int) Math.sqrt(arr.length);

        int bit[][] = new int[blockSize+1][MAX];
        buildArray(arr, blockSize, arr.length, bit);

        System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));

        queryUpdate(2, 8, blockSize, arr, bit);

        System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));

        queryUpdate(4, 3, blockSize, arr, bit);

        queryUpdate(1, 3, blockSize, arr, bit);

        System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));

    }
}
1
2
1

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

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

O (1) ສຳ ລັບການປັບປຸງອາເລແລະ O (n) ສຳ ລັບການພິມຂບວນ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ບັນຫາ“ ຈຳ ນວນຂອງອົງປະກອບນ້ອຍກວ່າຫລືເທົ່າກັບ ຈຳ ນວນທີ່ໃຫ້ໄວ້ໃນອະວະກາດທີ່ໃຫ້ໄວ້” ມີພື້ນທີ່ເສັ້ນຊື່.