په بائنری صف کې پوښتنې حساب او ٹوگل کړئ


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon فیسبوک د ګوګل über
پیشه برخه - ونې

An سور د اندازې n د ننوت ارزښت په توګه ورکړل شوی دی. ستونزه "د بائنری صفونو په اړه د پوښتنو او شمیرو پوښتنې" پوښتنه کوي چې ځینې پوښتنې ترسره کوي چې لاندې ورکړل شوي ، پوښتنې کولی شي په تصادفي ډول توپیر ولري.

پوښتنې ⇒ دي

د ټوگل پوښتنې ⇒ ٹوگل کول (پیل کول ، پای کول) ، د دې ٹوگل پوښتنې معنی لري ، 0 ورکړل شوي حد کې 1s 1 یا 0s XNUMX ته بدل کړئ.

د شمېرنې شمیره ⇒ شمیره (پیل ، پای) ، د دې شمېرنې پوښتنې پدې معنی دي چې په ورکړل شوي حد کې د ټولو شمیرنو شمیرل دي.

بېلګه

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. چیک کړئ چې بولین boolTree سمه ده که غلط. که دا ریښتیا وي نو نوډ ته د غلط په توګه نښه کړئ. ارزښت په کې تازه کړئ برخه د پای په توګه - د + 1 برخې برخې ونې [نوډ].
  2. وګوره که دا د پا nې نوډ نه وي ، نو بیا یې ترتیب کړئ یا بدل کړئ boolTree د ماشومانو.
  3. که ارزښتونه له حد څخه بهر وي ، نو بیرته راشئ.
  4. وګوره که برخه په حد کې راشئ ، که ریښتیا وي ، نو د فرق په توګه د برخې برخې ونې اوسني عنصر تازه کړئ او بیا یې چیک کړئ که دا د پا nې نوډ نه وي ، او ورته مرحله په مرحله 2 کې ترسره کړئ.
  5. وګوره که سیګارت ټری حد کې نه وي او ارزښتونه د برخې برخې په دواړو خواوو کې تیریږي نو بیا تکراري زنګ ووهئ.
  6. د دوی د پایلو په توګه د سیګنډری ټری نوډ اوسني نوډ ارزښت تازه کړئ.

د شمېرنې پوښتنې لپاره

  1. وګوره که موجوده نوډ له حد څخه بهر وي ، نو 0 ته راستون شئ.
  2. بیا وګورئ چې د بولټریز اوسني نوډ ریښتیا دی ، که ریښتیا وي ، نو د بولټریز اوسني نوډ په غلط نښه کړئ او د برخې په توګه د حوزې موجوده نوډ ارزښت تازه کړئ.
  3. وګورئ چې آیا دا د پا nې تذکره نده او د ماشومانو ارزښتونه الوزوي.
  4. وګوره چې که سیګام ټری په ورکړل شوې اندازې کې پروت وي ، نو بیا یې سیګامیټری [نوډ] بیرته ورکړئ.
  5. که نه نو بیا په تکراري ډول فنکشن ته زنګ ووهئ چې دا له مینځه نه ځي.

تشریح

موږ د n یو لړ درکړ چې دا ټول ارزښتونه 0 ته پیل شوي. موږ به دوه پوښتنو ته د ترسره کولو په اړه ورکړو چې د پوښتنې بدلولو هڅه کوو کوم چې په 0s 1 او ټول 1s په ټاکل شوي حد کې دننه بدلوي. . د شمېرنې پوښتنې د ورکړل شوي حد کې موجود ټولو صفرونو حساب کول دي. موږ سیګمټریټ کاروو چې د 0 په توګه پیژندل شوی. نو موږ دا د 0s حد کې بدل کړو.

هرکله چې د توګال فنکشن ته ویل کیږي ، موږ به د بولین اری په لټه کې شو چې موږ د بول ټری په توګه رامینځته کړي کوم چې د غلط په توګه پیل شوی و ، موږ به وګورو چې ایا د بولټری اوسنی نوډ ارزښت ریښتینی دی یا غلط ، که دا غلط معنی ولري نو کوم یو یې لري تر دې دمه نه دی شوی. نو موږ اړتیا لرو چې دا وکړو ، او که دا ریښتیا وي ، لومړی یې موږ غلط وګ markو ، نو موږ به وروسته ترې ګټه واخلو ، او په اوسني نوډ کې د برخې برخې ونې ارزښت تازه کړو د پای او پیل د توپیر مجموعې په توګه او د 1 او اوسني نوډ د سیګیمټری ارزښت ارزښت. موږ به وګورو چې ایا دا د پا nو تذکره نده ، ځکه چې که دا وي ، نو موږ به وروسته د دې عملیات نه کوو. که دا نه وي ، نو بیا به موږ د بولین ارزښتونو په توګه د ماشومانو نوډ ارزښتونه تازه کړو.

که چیرې د سیګنټری اوسنۍ برخه په ورکړل شوې اندازې کې وي که نه. که نه نو د داسې لپاره تکراري زنګونه وکړئ چې د نوډونو برخه د ورکړل شوي حد کې راځي.

ورته شی د شمېرنې فعالیت سره ترسره کول دي مګر د یو څه توپیر لید سره. موږ به وګورو چې اوسني نوډ باید له حد څخه بهر نه وي که چیرې دا بیا په ساده ډول 0 ارزښت بیرته راشي.

وګوره که اوسني نوډ باید د حوزې اوسني نوډ سره نښه نشي. که ریښتیا وي نو اوسني نوډ د غلط په توګه تازه کړئ ، او د حوزې اوسني نوډ ارزښتونه تازه کړئ د پای او پیل کولو توپیر او د 1 او اوسني نوډ فرق توپیر چې موږ یې د ټګینګ فعالیت کې ترسره کړی ، بیا چیک کول دا دي پا leafه نده ، بیا د ماشومانو نوډونو تازه کولو سره پرمخ ځئ. تر دې دمه پدې مرحله کې ، موږ د ځواب بیرته راستنولو لپاره ټول مخکینۍ میتودونه ترسره کړل ، د دې لپاره موږ به وګورو چې آیا د نوډونو اوسنۍ برخه په ورکړل شوي حد کې موقعیت لري او د سیجمنټری نوډ اوسنی ارزښت بیرته راګرځوي. نور په تکراري ډول غږ کوي چې دا حد کې دننه کړي.

تطبیق

په بائنری صف کې د پوښتنو شمیره او ٹوگل کولو لپاره 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

په جایزی کوډ د بائنری صفونو کې پوښتنې د شمیرو او توګلو لپاره

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) هلته "ق" دا د پوښتنو شمیره ده او "n" د صفونو کچه ده.

د ځای پیچلتیا

اې (N) هلته "n" د صفونو کچه ده.

ماخذ