Хоёртын массив дээрх асуулга тоолж, сэлгэх


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны Facebook-ийн Google-ийн Uber
Array Сегмент мод

An массив n хэмжээтэй оролтын утга өгсөн болно. "Хоёртын массив дээрх асуулгуудыг тоолж, асаах" асуудал нь доор өгөгдсөн зарим асуултуудыг гүйцэтгэхийг хүсдэг тул асуулга нь санамсаргүй байдлаар өөр өөр байж болно.

Асуултууд нь ⇒

Асуулгыг асаах g сэлгэх (эхлэх, дуусах), энэ асуулга нь өгөгдсөн муж дотор 0-ийг 1 эсвэл 1-ийг 0 болгож өөрчлөхийг хэлнэ.

Count query ⇒ count (эхлэх, дуусах), энэ тооллогын асуулга нь өгөгдсөн муж доторх бүх тоог тоолохыг хэлнэ.

Жишээ нь

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.

Тайлбар: Асуулт бүр дээр нэгийн тоог хэвлэв.

Хоёртын массив дээрх асуулга тоолж, сэлгэх

Алгоритм

  1. Boolean эсэхийг шалгана уу boolTree үнэн эсвэл худал. Хэрэв энэ нь үнэн бол тэр зангилааг худал гэж тэмдэглэ. Дахь утгыг шинэчлэх мод мод төгсгөл байдлаар - эхлэх + 1 сегментМод [зангилаа].
  2. Энэ нь навчны зангилаа биш эсэхийг шалгаад дараа нь утгыг нь тохируулж эсвэл эргүүлээрэй boolTree хүүхдүүдийн.
  3. Хэрэв утгууд хязгаараас хэтэрсэн бол буцаана уу.
  4. Эсэхийг шалгана уу мод мод Хэрэв үнэн бол мужид ороод сегментийн модны одоогийн элементийн ялгааг шинэчилж, навчны зангилаа биш эсэхийг дахин шалгаж, 2-р алхамтай адил процедурыг хий.
  5. SegmentTree нь муж дотор байхгүй байгаа ба segmentTree-ийн хоёр талд утгууд байгаа эсэхийг шалгаад рекурсив дуудлага хийнэ үү.
  6. Сегментийн модны зангилааны одоогийн зангилааны утгыг үр хүүхдүүд нь шинэчилнэ.

Тоолох асуулгын хувьд

  1. Одоогийн зангилаа мужаас гарсан эсэхийг шалгаад 0-ийг буцаана уу.
  2. BoolTrees-ийн одоогийн зангилаа үнэн эсэхийг, үнэн бол boolTrees-ийн одоогийн зангилааг худал гэж тэмдэглээд сегментийн модны одоогийн зангилааны утгыг ялгавар болгон шинэчил.
  3. Энэ нь навчны зангилаа биш эсэхийг шалгаж, хүүхдүүдийн утгыг эргүүлнэ.
  4. SegmentTree нь өгөгдсөн муж дотор байгаа эсэхийг шалгаад segmentTree [зангилаа] -г буцаана.
  5. Хэрэв үгүй ​​бол функцийг давхцахгүйн тулд рекурсив байдлаар дуудах хэрэгтэй.

Тайлбар

Бид бүх массын утгыг 0 гэж эхлүүлсэн байхаар n массивыг өгсөн болно. Бид шилжүүлсэн асуулга болох хоёр асуултыг өгөх бөгөөд энэ нь өгөгдсөн муж доторх бүх 0-ийг 1-д, бүх 1-ийг 0-д хөрвүүлэх явдал юм. . Тоолох асуулга нь өгөгдсөн муж дотор байгаа бүх тэгийг тоолох явдал юм. Бид 0 гэж эхлүүлсэн segmentTree-ийг ашиглах гэж байна. Тиймээс бид үүнийг муж дотор 1 болгон хөрвүүлнэ.

Сэлгэх функц дуудагдсан тохиолдолд бид boolTree хэлбэрээр үүсгэсэн Boolean массивыг хуурамчаар эхлүүлсэн байхыг хайж олох болно. өнөөг хүртэл хийгдээгүй байна. Тиймээс бид үүнийг хийх хэрэгтэй бөгөөд хэрэв энэ нь үнэн бол бид үүнийг хуурамч гэж тэмдэглэсэн тул дараа нь ашиглаж, одоогийн зангилаан дахь segmentTree-ийн утгыг төгсгөл ба эхлэх зөрүүний нийлбэрээр шинэчилж болно. мөн сегментийн модны 1 ба одоогийн зангилааны утгын зөрүү. Энэ нь навчны зангилаа биш эсэхийг шалгаж байх болно, учир нь ийм бол дараа нь үйл ажиллагаа явуулахгүй. Хэрэв тийм биш бол бид хүүхдүүдийн зангилааны утгыг Boolean утга болгон шинэчлэх болно.

SegmentTree-ийн одоогийн сегмент нь өгөгдсөн хязгаарт байгаа эсэхийг шалгана уу. Хэрэв үгүй ​​бол зангилааны сегмент нь өгөгдсөн хязгаарт багтахын тулд рекурсив дуудлага хийнэ.

Үүнтэй ижил зүйл бол тоолох функцтэй холбоотой боловч арай өөр аргаар хандах явдал юм. Хэрэв бид 0 утгыг буцааж өгвөл одоогийн зангилаа хязгаараас хэтрэхгүй байх ёстой.

Одоогийн зангилааны сегментийн одоогийн зангилаагаар тэмдэглэгдэх ёсгүй эсэхийг шалгана уу. Хэрэв үнэн бол одоогийн зангилааг худал гэж шинэчилж, сегмент модны одоогийн зангилааны утгыг төгсгөл ба эхлэх зөрүүний нийлбэр болон сегментийн 1 ба одоогийн зангилааны зөрүүний нийлбэрээр шинэчилнэ үү. навч биш, дараа нь хүүхдүүдийн зангилаа шинэчлэгдэн урагшилна. Одоогийн байдлаар бид хариултыг буцааж өгөх урьдчилсан урьдчилсан аргуудыг бүгдийг нь хийсэн бөгөөд ингэснээр зангилааны одоогийн сегмент нь өгөгдсөн хязгаарт байгаа эсэхийг шалгаж, segementTree зангилааны одоогийн утгыг буцааж өгөх болно. Бусад нь функцийг хязгаарт багтаахын тулд рекурсив байдлаар дууддаг.

Хэрэгжүүлэх

Хоёртын массив дээрх асуулга тоолох, сэлгэх C ++ код

#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 код

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

Хоёртын массив дээрх асуултуудыг тоолж, асаахад зориулсан нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (q * log n) хаана "Q" гэсэн асуултын тоо ба "N" нь массивын хэмжээ юм.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массивын хэмжээ юм.

лавлагаа