ນັບແລະສະຫຼັບການສອບຖາມກ່ຽວກັບ Array Arinary


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ເຟສບຸກ ກູໂກ Uber
Array Segment-Tree

An array ຂອງຂະຫນາດ n ໄດ້ຖືກມອບໃຫ້ເປັນມູນຄ່າການປ້ອນຂໍ້ມູນ. ບັນຫາ“ ການນັບແລະສະຫຼັບການສອບຖາມກ່ຽວກັບຖານຂໍ້ມູນຖານສອງ” ຂໍໃຫ້ປະຕິບັດບາງ ຄຳ ຖາມທີ່ໃຫ້ຢູ່ດ້ານລຸ່ມ, ການສອບຖາມສາມາດແຕກຕ່າງກັນໃນແບບສຸ່ມ.

ການສອບຖາມແມ່ນ⇒

ການສະຫຼັບການສອບຖາມ⇒ສະຫຼັບ (ເລີ່ມຕົ້ນ, ສິ້ນສຸດລົງ), ການສອບຖາມສະຫຼັບນີ້ ໝາຍ ຄວາມວ່າ, ປ່ຽນ 0s ເປັນ 1 ຫຼື 1s ເປັນ 0s ພາຍໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້

ການນັບ ຄຳ ຖາມ - ນັບ (ເລີ່ມຕົ້ນ, ສິ້ນສຸດ), ການສອບຖາມນັບ ຈຳ ນວນນີ້ ໝາຍ ຄວາມວ່ານັບ ຈຳ ນວນທັງ ໝົດ ຂອງ ຈຳ ນວນທີ່ຢູ່ໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້.

ຍົກຕົວຢ່າງ

n = 5
toggle(0, 1)
toggle(2, 3)
count(1, 2)
toggle(1, 4)
count(0, 2)
Count of all the ones within the range 1 and 2 is 2.
The count of all the ones within the range 0 and 2 is 1.

ຄໍາອະທິບາຍ: ຈຳ ນວນ ໜຶ່ງ ຖືກພິມອອກໃນແຕ່ລະ ຄຳ ຖາມນັບ.

ນັບແລະສະຫຼັບການສອບຖາມກ່ຽວກັບ Array Arinary

ລະບົບວິເຄາະ

  1. ກວດເບິ່ງວ່າ Boolean boolTree ແມ່ນຄວາມຈິງຫຼືຜິດ. ຖ້າມັນແມ່ນຄວາມຈິງແລ້ວໃຫ້ ໝາຍ ວ່າຂໍ້ນັ້ນບໍ່ຖືກຕ້ອງ. ປັບປຸງຄຸນຄ່າໃນ ຕອນ ເປັນສິ້ນສຸດ - ເລີ່ມຕົ້ນ + 1 segmentTree [node].
  2. ກວດເບິ່ງວ່າມັນບໍ່ແມ່ນໃບຂອງໃບ, ຫຼັງຈາກນັ້ນຕັ້ງຫລືປ່ຽນຄ່າຂອງ boolTree ຂອງເດັກນ້ອຍ.
  3. ຖ້າຄຸນຄ່າບໍ່ຢູ່ໃນຂອບເຂດ, ແລ້ວກັບຄືນມາ.
  4. ໃຫ້ກວດເບິ່ງວ່າ ຕອນ ເຂົ້າມາໃນຂອບເຂດ, ຖ້າເປັນຄວາມຈິງ, ແລ້ວປັບປຸງມູນຄ່າປັດຈຸບັນຂອງ segmentTree ເປັນຄວາມແຕກຕ່າງແລະກວດເບິ່ງອີກຄັ້ງຖ້າມັນບໍ່ແມ່ນໃບໃບ, ແລະເຮັດຂັ້ນຕອນດຽວກັນກັບໃນຂັ້ນຕອນ 2.
  5. ກວດເບິ່ງວ່າ segmentTree ບໍ່ຢູ່ໃນຂອບເຂດແລະຄຸນຄ່າແມ່ນ ກຳ ລັງລິງຢູ່ຂ້າງຂອງ segmentTree ທັງສອງແນວໃດຫຼັງຈາກນັ້ນກໍ່ໂທເຂົ້າຫາ.
  6. ປັບປຸງມູນຄ່າຂອງ node ປັດຈຸບັນຂອງ segmentTree node ທີ່ລູກຂອງພວກເຂົາສົ່ງຜົນ.

ສຳ ລັບການສອບຖາມນັບ

  1. ກວດເບິ່ງວ່າ node ປັດຈຸບັນບໍ່ຢູ່ໃນຂອບເຂດ, ແລ້ວສົ່ງຄືນ 0.
  2. ຫຼັງຈາກນັ້ນໃຫ້ເບິ່ງວ່າ node ຂອງ boolTrees ປະຈຸບັນແມ່ນຖືກຕ້ອງຫຼືບໍ່, ຖ້າຖືກຕ້ອງ, ແລ້ວໃຫ້ ໝາຍ ໃສ່ node ຂອງ boolTrees ໃນປະຈຸບັນທີ່ບໍ່ຖືກຕ້ອງແລະອັບເດດຄ່າ node ປັດຈຸບັນຂອງ segmentTree ເປັນຄວາມແຕກຕ່າງ
  3. ກວດເບິ່ງວ່າມັນບໍ່ແມ່ນເສັ້ນໃບແລະປ່ຽນຄຸນຄ່າຂອງເດັກນ້ອຍບໍ?
  4. ກວດເບິ່ງວ່າ segmentTree ນອນຢູ່ໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້, ຫຼັງຈາກນັ້ນສົ່ງຄືນ segmentTree [node].
  5. ຖ້າບໍ່ແມ່ນຫຼັງຈາກນັ້ນເອີ້ນຄືນການເຮັດວຽກເພື່ອບໍ່ໃຫ້ມັນຊໍ້າຊ້ອນ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ໃຫ້ແຖວຂອງ n ເຊັ່ນວ່າຄ່າຂອງມັນທັງ ໝົດ ແມ່ນເລີ່ມຕັ້ງແຕ່ 0. ພວກເຮົາ ກຳ ລັງ ດຳ ເນີນການສອບຖາມສອງຢ່າງທີ່ສະຫຼັບການສອບຖາມເຊິ່ງແມ່ນເພື່ອປ່ຽນທຸກ 0s ເຂົ້າໃນ 1s ແລະທັງ ໝົດ 1s ເຂົ້າ 0s ພາຍໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້ . ການສອບຖາມນັບແມ່ນເພື່ອນັບທຸກໆສູນທີ່ມີຢູ່ພາຍໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້. ພວກເຮົາຈະໃຊ້ segmentTree ເຊິ່ງເລີ່ມຕົ້ນເປັນ 0. ດັ່ງນັ້ນເຮົາຈະປ່ຽນເປັນ 1s ພາຍໃນຂອບເຂດ.

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

ກວດເບິ່ງວ່າສ່ວນປະຈຸບັນຂອງ SegmentTree ແມ່ນຢູ່ໃນຂອບເຂດໃດ ໜຶ່ງ ຫຼືບໍ່. ຖ້າບໍ່ແມ່ນຫຼັງຈາກນັ້ນຮຽກຮ້ອງການຮຽກຮ້ອງເພື່ອຮຽກຮ້ອງໃຫ້ພາກສ່ວນຂໍ້ມູນນັ້ນເຂົ້າມາໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້.

ສິ່ງດຽວກັນແມ່ນເຮັດກັບ ໜ້າ ທີ່ນັບແຕ່ມີວິທີການທີ່ແຕກຕ່າງກັນເລັກນ້ອຍ. ພວກເຮົາຈະກວດສອບແມ່ນ node ປັດຈຸບັນບໍ່ຄວນຢູ່ນອກຂອບເຂດຖ້າມັນພຽງແຕ່ສົ່ງຄືນຄ່າ 0 ເທົ່ານັ້ນ.

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

ການປະຕິບັດ

ລະຫັດ C ++ ເພື່ອນັບແລະສະຫຼັບການສອບຖາມກ່ຽວກັບ Array Arinary

#include<iostream>
using namespace std;

const int MAX = 100000;

int segmentTree[MAX] = {0};

bool boolTree[MAX] = {false};

void toggle(int node, int starting, int ending, int rangeStart, int rangeEnding)
{
    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending - starting + 1 - segmentTree[node];

        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
    }
    if (starting>ending || rangeStart > ending || rangeEnding < starting)
        return ;
    if (rangeStart<=starting && ending<=rangeEnding)
    {
        segmentTree[node] = ending-starting+1 - segmentTree[node];
        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
        return;
    }
    int mid = (starting+ending)/2;
    toggle((node<<1), starting, mid, rangeStart, rangeEnding);
    toggle((node<<1)+1, mid+1,ending, rangeStart, rangeEnding);
    if (starting < ending)
        segmentTree[node] = segmentTree[node<<1] + segmentTree[(node<<1)+1];
}

int count(int node, int starting, int ending, int qs, int qe)
{
    if (starting>ending || qs > ending || qe < starting)
        return 0;

    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending-starting+1-segmentTree[node];

        if (starting<ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[(node<<1)+1] = !boolTree[(node<<1)+1];
        }
    }
    if (qs<=starting && ending<=qe)
        return segmentTree[node];

    int mid = (starting+ending)/2;
    return count((node<<1), starting, mid, qs, qe) +
           count((node<<1)+1, mid+1, ending, qs, qe);
}

int main()
{
    int n = 5;
    toggle(1, 0, n-1, 0, 1);
    toggle(1, 0, n-1, 2, 3);
    cout << count(1, 0, n-1, 1, 2) << endl;
    toggle(1, 0, n-1, 1, 4);
    cout << count(1, 0, n-1, 0, 2) << endl;

    return 0;
}
2
1

ລະຫັດ Java ເພື່ອ Count ແລະສະຫຼັບການສອບຖາມກ່ຽວກັບ Array Arinary

class toggleAndCount
{
    static final int MAX = 100000;

    static int segmentTree[] = new int[MAX];

    static boolean boolTree[] = new boolean[MAX];

    static void toggle(int node, int starting,int ending, int rangeStart, int rangeEnding)
    {
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
        }
        if (starting > ending || rangeStart > ending || rangeEnding < starting)
        {
            return;
        }
        if (rangeStart <= starting && ending <= rangeEnding)
        {
            segmentTree[node] = ending - starting + 1 - segmentTree[node];
            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
            return;
        }

        int mid = (starting + ending) / 2;
        toggle((node << 1), starting, mid, rangeStart, rangeEnding);
        toggle((node << 1) + 1, mid + 1, ending, rangeStart, rangeEnding);
        if (starting < ending)
        {
            segmentTree[node] = segmentTree[node << 1] +segmentTree[(node << 1) + 1];
        }
    }
    static int count(int node, int starting,int ending, int qs, int qe)
    {
        if (starting > ending || qs > ending || qe < starting)
        {
            return 0;
        }
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[(node << 1) + 1] = !boolTree[(node << 1) + 1];
            }
        }
        if (qs <= starting && ending <= qe)
        {
            return segmentTree[node];
        }
        int mid = (starting + ending) / 2;
        return count((node << 1), starting, mid, qs, qe) + count((node << 1) + 1, mid + 1, ending, qs, qe);
    }
    public static void main(String args[])
    {
        int n = 5;

        toggle(1, 0, n-1, 0, 1);
        toggle(1, 0, n-1, 2, 3);
        System.out.println( count(1, 0, n-1, 1, 2));
        toggle(1, 0, n-1, 1, 4);
        System.out.println(count(1, 0, n-1, 0, 2));
    }
}

2
1

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການນັບ ຈຳ ນວນແລະສະຫຼັບການສອບຖາມກ່ຽວກັບ Array Arinary

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

O (q * log n) ບ່ອນທີ່ "Q" ແມ່ນ ຈຳ ນວນ ຄຳ ຖາມແລະ "n" ແມ່ນຂະ ໜາດ ຂອງຂບວນ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນຂະ ໜາດ ຂອງຂບວນ.

ກະສານອ້າງອີງ