ثنائی صف پر سوالات گنیں اور ٹوگل کریں


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون فیس بک گوگل Uber
لڑی قطعہ درخت

An صف سائز ن کو ایک ان پٹ قدر کے طور پر دیا گیا ہے۔ "بائنری صف پر گنتی اور ٹوگل سوالات" مسئلہ کچھ سوالات کو انجام دینے کے لئے کہتا ہے جو ذیل میں دیئے گئے ہیں ، سوالات بے ترتیب انداز میں مختلف ہوسکتے ہیں۔

سوالات ⇒ ہیں

ٹوگل استفسار ⇒ ٹوگل (شروع ، اختتام پذیر) ، اس ٹوگل استفسار کا مطلب ہے ، 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.

وضاحت: ایک گنتی ہر گنتی کے سوال پر چھپی ہوئی ہے۔

ثنائی صف پر سوالات گنیں اور ٹوگل کریں

الگورتھم

  1. چیک کریں اگر بولین ہے boolTree سچ ہے یا غلط۔ اگر یہ سچ ہے تو اس نوڈ کو جھوٹا کے طور پر نشان زد کریں۔ میں قدر کو اپ ڈیٹ کریں طبقہ اختتام پذیر ہونے کے ساتھ - + 1 طبقہ درخت [نوڈ] شروع کرنا۔
  2. چیک کریں کہ آیا یہ لیف نوڈ نہیں ہے ، پھر سیٹ کریں یا اس کی ویلیو کو الٹ کریں boolTree بچوں کے.
  3. اگر قدریں حد سے زیادہ ہیں تو واپس آئیں۔
  4. چیک کریں اگر طبقہ حد میں آو ، اگر سچ ہے تو ، پھر فرق کے طور پر طبقہ کے درخت کے موجودہ موجودہ عنصر کو اپ ڈیٹ کریں اور دوبارہ چیک کریں کہ آیا یہ کوئی پتی کا نوڈ نہیں ہے ، اور وہی عمل کریں جیسے مرحلہ 2 میں ہے۔
  5. چیک کریں کہ اگر سیگمنٹ ٹری رینج میں نہیں ہے اور سیگمنٹ ٹری کے دونوں طرف قدریں لیپ ہو رہی ہیں تو پھر ریکارسیو کال کریں۔
  6. سیگمنٹ ٹری نوڈ کے موجودہ نوڈ کی قدر ان کے بچوں کے نتیجے میں تازہ کریں۔

گنتی کے سوال کے لئے

  1. چیک کریں کہ آیا موجودہ نوڈ حد سے باہر ہے ، پھر 0 واپس کریں۔
  2. پھر دیکھیں کہ کیا بولٹریز کا موجودہ نوڈ صحیح ہے ، اگر درست ہے تو ، پھر بولٹریز کے موجودہ نوڈ کو جھوٹ پر نشان زد کریں اور سیگمنٹ ٹری کی موجودہ نوڈ ویلیو کو فرق کے طور پر اپ ڈیٹ کریں۔
  3. چیک کریں کہ آیا یہ لیف نوڈ نہیں ہے اور بچوں کی اقدار کو پلٹائیں۔
  4. چیک کریں کہ اگر سیگمنٹ ٹری دی گئی حد میں ہے تو پھر سیگمنٹ ٹری [نوڈ] واپس کریں۔
  5. اگر نہیں تو پھر تکرار کے ساتھ فنکشن کو کال کریں تاکہ یہ اوورلپ نہ ہو۔

وضاحت

ہم نے n کی ایک صف دی ہے کہ اس کی تمام اقدار کو 0 سے شروع کردیا گیا ہے۔ ہم دو سوالات دے رہے ہیں جو ٹوگل استفسار ہیں جو تمام 0s کو 1s میں اور تمام 1s کو 0s میں تبدیل کرنے کے لئے دی گئی حد میں ہے۔ . گنتی استفسار یہ ہے کہ دی گئی حد میں موجود تمام زیرو کی گنتی کی جائے۔ ہم سیگمنٹ ٹری استعمال کرنے جارہے ہیں جس کی ابتدا 0. کے طور پر کی گئی ہے۔ لہذا ہم اسے حد میں 1s میں تبدیل کرتے ہیں۔

جب بھی ٹوگل فنکشن کہا جاتا ہے ، ہم بولی سرنی کو ڈھونڈیں گے جو ہم نے بول ٹری کی حیثیت سے تخلیق کیا تھا جس کی ابتداء جھوٹی کے طور پر کی گئی تھی ، ہم چیک کریں گے کہ اگر بول ٹری کی موجودہ نوڈ ویلیو صحیح ہے یا غلط ، اگر یہ غلط ہے اس کا مطلب ہے اپ ڈیٹس میں سے کسی کو اب تک نہیں کیا گیا ہے۔ لہذا ہمیں یہ کرنے کی ضرورت ہے ، اور اگر یہ سچ ہے تو سب سے پہلے ہم اسے جھوٹے کے بطور نشان زد کرتے ہیں ، لہذا ہم اسے بعد میں استعمال کرسکتے ہیں ، اور موجودہ نوڈ پر سیگمنٹ ٹری کی قیمت کو اپ ڈیٹ کرنے اور ختم ہونے اور شروع کرنے کے فرق کے جوہر کے طور پر اپ ڈیٹ کرسکتے ہیں۔ اور سیگمنٹ ٹری کی 1 اور موجودہ نوڈ کی قدر کا فرق۔ ہم اس کی جانچ پڑتال کریں گے کہ آیا یہ لیف نوڈ نہیں ہے ، کیونکہ اگر یہ ہے تو ، ہم اس کے بعد آپریشن نہیں کریں گے۔ اگر یہ نہیں ہے تو ، پھر ہم بچوں کے نوڈ کی اقدار کو بولین اقدار کی طرح اپ ڈیٹ کریں گے۔

چیک کریں کہ سیگمنٹ ٹری کا موجودہ طبقہ کسی مخصوص حد میں ہے یا نہیں۔ اگر نہیں تو پھر ایسی نوکریاں کالیں کریں جو نوڈس طبقہ دی گئی حد میں آئیں۔

ایک ہی چیز کاؤنٹی فنکشن کے ساتھ کرنا ہے لیکن تھوڑا سا مختلف نقطہ نظر کے ساتھ۔ ہم معائنہ کریں گے کہ موجودہ نوڈ کو حد سے باہر نہیں ہونا چاہئے اگر یہ پھر صرف 0 کی قیمت لوٹاتا ہے۔

چیک کریں کہ کیا موجودہ نوڈ کو سیگمنٹ ٹری کے موجودہ نوڈ کے ساتھ نشان زد نہیں کرنا چاہئے۔ اگر سچ ہے تو موجودہ نوڈ کو غلط کے طور پر اپ ڈیٹ کریں ، اور سیگمنٹ ٹری کی موجودہ نوڈ کی اقدار کو اپ ڈیٹ کریں اور ختم ہونے اور شروع کرنے کے فرق اور 1 اور سیجمنٹ ٹری کے موجودہ نوڈ کے فرق کے جو آپ نے ٹوگلنگ فنکشن میں کیا ہے ، اس کی دوبارہ جانچ پڑتال کریں۔ کوئی پتی نہیں ، پھر بچوں کے نوڈس کی تازہ کاری کے ساتھ آگے بڑھیں۔ ابھی تک اس مرحلے تک ، ہم نے جواب کو واپس کرنے کے لئے تمام ضروری طریقوں کو انجام دیا ہے ، اس کے لئے ہم یہ جاننے کے لئے جارہے ہیں کہ آیا نوڈس کا موجودہ طبقہ دیئے گئے حد میں ہے یا نہیں اور سیگمنٹ ٹری نوڈ کی موجودہ قیمت کو لوٹائے گا۔ بصورت دیگر اس فنکشن کو حدود میں رہنے کے ل. بار بار کہتے ہیں۔

عمل

بائنری صف پر سوالات گننے اور ٹوگل کرنے کیلئے 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) کہاں "ق" سوالات کی تعداد ہے اور "این" سرنی کا سائز ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" سرنی کا سائز ہے۔

حوالہ