বাইনারি অ্যারেতে প্রশ্নগুলি টগল করুন এবং টগল করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ফেসবুক গুগল উবার
বিন্যাস সেগমেন্ট-ট্রি

An বিন্যাস আকার এন এর একটি ইনপুট মান হিসাবে দেওয়া হয়েছে। "বাইনারি অ্যারেতে গণনা এবং টগল ক্যোয়ারী" সমস্যাটি নীচে প্রদত্ত কিছু প্রশ্নের সম্পাদন করতে বলে, প্রশ্নগুলি এলোমেলোভাবে পরিবর্তিত হতে পারে।

প্রশ্নগুলি হ'ল ⇒

টগল ক্যোয়ারী ⇒ টগল (শুরু, শেষ), এই টগল ক্যোয়ারির অর্থ, 0s কে 1 বা 1 এসকে 0 সেকেন্ডে পরিবর্তিত রেঞ্জের মধ্যে পরিবর্তন করুন।

গণনা ক্যোয়ারী ⇒ গণনা (শুরু করা, শেষ হওয়া), এই গণনা ক্যোয়ারির অর্থ প্রদত্ত সীমার মধ্যে থাকা সমস্ত সংখ্যাকে গণনা করা।

উদাহরণ

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. তারপরে দেখুন দেখুন যে boolTree এর বর্তমান নোডটি সত্য, যদি সত্য হয়, তবে boolTree এর বর্তমান নোডটিকে মিথ্যা হিসাবে চিহ্নিত করুন এবং সেগমেন্টট্রির বর্তমান নোড মানকে পার্থক্য হিসাবে আপডেট করুন।
  3. এটি কোনও লিফ নোড নয় কিনা তা পরীক্ষা করে দেখুন এবং বাচ্চাদের মানগুলি উল্টে দিন।
  4. সেগমেন্টটি ট্রি প্রদত্ত পরিসরে রয়েছে কিনা তা পরীক্ষা করে দেখুন, তারপরে সেগমেন্টটি ট্রি [নোড] দিন।
  5. যদি না হয় তবে পুনরাবৃত্তভাবে ফাংশনটি কল করুন যাতে এটি ওভারল্যাপ না হয়।

ব্যাখ্যা

আমরা এন এর একটি অ্যারে দিয়েছি যে এর সমস্ত মান 0 এ শুরু করা হয় আমরা দুটি টপিক প্রদান করতে যাচ্ছি যা টগল ক্যোয়ারী যা সমস্ত 0 গুলি 1s এর মধ্যে এবং সমস্ত 1 গুলি প্রদত্ত পরিসরের মধ্যে 0-এর বিপরীতে পরিণত হয় । গণনা কোয়েরিটি প্রদত্ত ব্যাপ্তির মধ্যে উপস্থিত সমস্ত শূন্যকে গণনা করা। আমরা সেগমেন্টটি ট্রি ব্যবহার করতে যা যা 0 হিসাবে আরম্ভ হয় তাই আমরা এটিকে 1 সীমাতে রূপান্তর করি।

যখনই টগল ফাংশনটি ডাকা হবে, আমরা বুলিয়ান অ্যারের সন্ধান করব যা আমরা বল্ট্রি হিসাবে তৈরি করেছি যা মিথ্যা হিসাবে শুরু করা হয়েছিল, আমরা পরীক্ষা করে দেখব যে বুলট্রি'র বর্তমান নোড মানটি সত্য বা মিথ্যা, যদি এটি মিথ্যা হয় তার মানে আপডেটগুলির মধ্যে কোনওটি রয়েছে এখন পর্যন্ত করা হয়নি। সুতরাং আমাদের এটি করা দরকার, এবং যদি এটি সত্য হয় তবে প্রথমত, আমরা এটিকে মিথ্যা হিসাবে চিহ্নিত করি, তাই আমরা পরে এটি ব্যবহার করতে পারি, এবং বর্তমান নোডে সেগমেন্টট্রির মান আপডেট এবং শুরু করার পার্থক্যের যোগফল হিসাবে আপডেট করতে পারি 1 এবং বর্তমান নোডের সেগমেন্টটি গাছের মানের পার্থক্য। এটি লিফ নোড না হলে আমরা খতিয়ে দেখব, কারণ যদি এটি হয় তবে আমরা এর পরে অপারেশন করব না। যদি তা না হয় তবে আমরা বাচ্চাদের নোডের মানগুলি বুলিয়ান মান হিসাবে আপডেট করব।

সেগমেন্টট্রি-র বর্তমান বিভাগটি নির্দিষ্ট রেঞ্জের মধ্যে রয়েছে কিনা তা পরীক্ষা করুন। যদি না হয় তবে এর জন্য পুনরাবৃত্ত কলগুলি করুন যাতে নোডগুলি সেগমেন্টের মধ্যে দেওয়া হয়।

একই জিনিসটি গণনা ফাংশনটির সাথে তবে কিছুটা ভিন্ন পদ্ধতির সাথে করা। আমরা খতিয়ে দেখব যে বর্তমান নোডটি সীমার বাইরে থাকা উচিত নয় যদি এটি কেবলমাত্র মান 0 দেয়।

বর্তমান নোডটি সেগমেন্টট্রি-র বর্তমান নোডের সাথে চিহ্নিত করা উচিত নয় কিনা তা পরীক্ষা করুন। যদি সত্য হয় তবে বর্তমান নোডটিকে মিথ্যা হিসাবে আপডেট করুন, এবং সেগমেন্টট্রি-র বর্তমান নোডের মানগুলি টগলিং ফাংশনে আমরা সম্পন্ন SegementTree এর 1 এবং বর্তমান নোডের পার্থক্যের যোগফল হিসাবে আপডেট করুন, আবার এটি পরীক্ষা করা হচ্ছে একটি পাতা নয়, তারপরে বাচ্চাদের নোডগুলির আপডেটের সাথে এগিয়ে যান। এখনও এই মুহুর্তে, আমরা উত্তরটি ফেরত দেওয়ার জন্য সমস্ত পূর্বশর্ত পদ্ধতি করেছি, তার জন্য আমরা পরীক্ষা করতে যাচ্ছি যে নোডের বর্তমান বিভাগটি প্রদত্ত পরিসরের মধ্যে রয়েছে কিনা এবং সেগমেন্ট্রি নোডের বর্তমান মানটি ফিরিয়ে দিচ্ছি। অন্যটি ক্রিয়াকলাপটিকে সীমার মধ্যে তৈরি করার জন্য পুনরাবৃত্তভাবে কল করে।

বাস্তবায়ন

বাইনারি অ্যারেতে প্রশ্নগুলি টগল করতে এবং টগল করতে সি ++ কোড

#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

বাইনারি অ্যারেতে গণনা এবং টগল ক্যোয়ারির জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (কিউ লগ এন) কোথায় "Q" এর প্রশ্নের সংখ্যা এবং "এন" অ্যারের আকার হয়।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারের আকার হয়।

উল্লেখ