ഒരു ബൈനറി അറേയിൽ ചോദ്യങ്ങൾ എണ്ണുകയും ടോഗിൾ ചെയ്യുകയും ചെയ്യുക  


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫേസ്ബുക്ക് ഗൂഗിൾ യൂബർ
അറേ സെഗ്മെന്റ്-ട്രീ

An ശ്രേണി വലുപ്പം n ഒരു ഇൻപുട്ട് മൂല്യമായി നൽകിയിരിക്കുന്നു. “ഒരു ബൈനറി അറേയിലെ ചോദ്യങ്ങൾ എണ്ണുകയും ടോഗിൾ ചെയ്യുകയും ചെയ്യുക” എന്ന പ്രശ്നം ചുവടെ നൽകിയിരിക്കുന്ന ചില ചോദ്യങ്ങൾ നടത്താൻ ആവശ്യപ്പെടുന്നു, ചോദ്യങ്ങൾ ക്രമരഹിതമായി വ്യത്യാസപ്പെടാം.

ചോദ്യങ്ങൾ are

ചോദ്യം ടോഗിൾ ചെയ്യുക (ടോഗിൾ ചെയ്യുക (ആരംഭിക്കുന്നു, അവസാനിക്കുന്നു), ഈ ടോഗിൾ അന്വേഷണം അർത്ഥമാക്കുന്നത്, നൽകിയ പരിധിക്കുള്ളിൽ 0 സെ 1 അല്ലെങ്കിൽ 1 സെ ആയി മാറ്റുക.

എണ്ണം അന്വേഷിക്കുക ⇒ എണ്ണം (ആരംഭിക്കുന്നു, അവസാനിക്കുന്നു), ഈ എണ്ണം അന്വേഷണം അർത്ഥമാക്കുന്നത് തന്നിരിക്കുന്ന പരിധിക്കുള്ളിലെ എല്ലാ എണ്ണങ്ങളും എണ്ണുക എന്നതാണ്.

ഉദാഹരണം  

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. ഇല്ലെങ്കിൽ, ഓവർലാപ്പ് ചെയ്യാതിരിക്കാൻ ആവർത്തിച്ച് വിളിക്കുക.

വിശദീകരണം  

അതിന്റെ എല്ലാ മൂല്യങ്ങളും 0 ലേക്ക് സമാരംഭിക്കുന്ന തരത്തിൽ ഞങ്ങൾ n ന്റെ ഒരു ശ്രേണി നൽകിയിട്ടുണ്ട്, ടോഗിൾ അന്വേഷണം നൽകുന്ന രണ്ട് ചോദ്യങ്ങൾ ഞങ്ങൾ നൽകാൻ പോകുന്നു, അത് എല്ലാ 0 കളെയും 1 സെയിലേക്കും എല്ലാ 1 കളെയും 0 സെയിലേക്ക് നൽകി. . തന്നിരിക്കുന്ന പരിധിക്കുള്ളിലുള്ള എല്ലാ പൂജ്യങ്ങളും എണ്ണുക എന്നതാണ് എണ്ണം അന്വേഷണം. 0 ആയി സമാരംഭിച്ച സെഗ്മെന്റ് ട്രീ ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു. അതിനാൽ ഞങ്ങൾ അതിനെ പരിധിക്കുള്ളിൽ 1 സെ ആയി പരിവർത്തനം ചെയ്യുന്നു.

ടോഗിൾ ഫംഗ്ഷൻ വിളിക്കുമ്പോഴെല്ലാം, ഞങ്ങൾ ബൂൾട്രീ ആയി സൃഷ്ടിച്ച ബൂലിയൻ അറേ തിരയുന്നു, അത് തെറ്റാണെന്ന് സമാരംഭിച്ചു, ബൂൾട്രീയുടെ നിലവിലെ നോഡ് മൂല്യം ശരിയാണോ തെറ്റാണോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും, അത് തെറ്റാണെങ്കിൽ ഏതെങ്കിലും അപ്‌ഡേറ്റുകൾ ഉണ്ടോ ഇപ്പോൾ വരെ ചെയ്തിട്ടില്ല. അതിനാൽ ഞങ്ങൾ ഇത് ചെയ്യേണ്ടതുണ്ട്, അത് ശരിയാണെങ്കിൽ, ഒന്നാമതായി, ഞങ്ങൾ അത് തെറ്റാണെന്ന് അടയാളപ്പെടുത്തുന്നു, അതിനാൽ നമുക്ക് ഇത് പിന്നീട് ഉപയോഗിക്കാം, കൂടാതെ അവസാനിക്കുന്നതിന്റെയും ആരംഭിക്കുന്നതിന്റെയും വ്യത്യാസത്തിന്റെ ആകെത്തുകയായി നിലവിലെ നോഡിലെ സെഗ്മെന്റ് ട്രീയുടെ മൂല്യം അപ്‌ഡേറ്റ് ചെയ്യുക. 1 ന്റെ വ്യത്യാസവും സെഗ്‌മെൻറ് ട്രീയുടെ നിലവിലെ നോഡിന്റെ മൂല്യവും. ഇത് ഒരു ഇല നോഡ് അല്ലയോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും, കാരണം അങ്ങനെയാണെങ്കിൽ, അതിനുശേഷം ഞങ്ങൾ പ്രവർത്തനങ്ങൾ നടത്തുകയില്ല. അങ്ങനെയല്ലെങ്കിൽ, ഞങ്ങൾ കുട്ടികളുടെ നോഡിന്റെ മൂല്യങ്ങൾ ബൂളിയൻ മൂല്യങ്ങളായി അപ്‌ഡേറ്റ് ചെയ്യും.

ഇതും കാണുക
തന്നിരിക്കുന്ന അറേയുടെ ഏതെങ്കിലും ഉപസെറ്റിന്റെ ആകെത്തുകയായി പ്രതിനിധീകരിക്കാൻ കഴിയാത്ത ഏറ്റവും ചെറിയ പോസിറ്റീവ് സംഖ്യ മൂല്യം കണ്ടെത്തുക

  

സെഗ്‌മെൻറ് ട്രീയുടെ നിലവിലെ സെഗ്‌മെന്റ് ഒരു നിശ്ചിത പരിധിക്കുള്ളിലാണോ അല്ലയോ എന്ന് പരിശോധിക്കുക. ഇല്ലെങ്കിൽ, നൽകിയ പരിധിക്കുള്ളിൽ നോഡ്സ് സെഗ്മെന്റ് വരുന്ന തരത്തിൽ ആവർത്തിച്ചുള്ള കോളുകൾ ചെയ്യുക.

ക function ണ്ട് ഫംഗ്ഷനുമായി ബന്ധപ്പെട്ടതാണെങ്കിലും അല്പം വ്യത്യസ്തമായ സമീപനത്തോടെയാണ് ഇത് ചെയ്യുന്നത്. നിലവിലെ നോഡ് 0 മൂല്യം നൽകിയാൽ അത് പരിധിക്ക് പുറത്തായിരിക്കരുത് എന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു.

സെഗ്‌മെൻറ് ട്രീയുടെ നിലവിലെ നോഡിനൊപ്പം നിലവിലെ നോഡ് അടയാളപ്പെടുത്തേണ്ടതില്ലേ എന്ന് പരിശോധിക്കുക. ശരിയാണെങ്കിൽ നിലവിലെ നോഡിനെ തെറ്റായി അപ്‌ഡേറ്റുചെയ്യുക, അവസാനിക്കുന്നതിന്റെയും ആരംഭിക്കുന്നതിന്റെയും വ്യത്യാസത്തിന്റെ ആകെത്തുകയായ സെഗ്‌മെൻ‌ട്രീയുടെ നിലവിലെ നോഡിന്റെ മൂല്യങ്ങളും അപ്‌ഡേറ്റ് ചെയ്യുക ഒരു ഇലയല്ല, തുടർന്ന് കുട്ടികളുടെ നോഡുകളുടെ അപ്‌ഡേറ്റുമായി മുന്നോട്ട് പോകുക. ഈ ഘട്ടത്തിൽ‌, ഉത്തരം നൽ‌കുന്നതിനുള്ള എല്ലാ മുൻ‌വ്യവസ്ഥകളും ഞങ്ങൾ‌ ചെയ്‌തു, അതിനായി നോഡുകളുടെ നിലവിലെ സെഗ്‌മെൻറ് തന്നിരിക്കുന്ന പരിധിക്കുള്ളിലാണോയെന്ന് പരിശോധിച്ച് സെഗ്‌മെൻറ് ട്രീ നോഡിന്റെ നിലവിലെ മൂല്യം തിരികെ നൽകും. പരിധിക്കുള്ളിൽ പ്രവർത്തിക്കുന്നതിന് ഫംഗ്ഷൻ ആവർത്തിച്ച് വിളിക്കുന്നു.

നടപ്പിലാക്കൽ  

ഒരു ബൈനറി അറേയിലെ ചോദ്യങ്ങൾ എണ്ണാനും ടോഗിൾ ചെയ്യാനുമുള്ള സി ++ കോഡ്

#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) എവിടെ "Q" ചോദ്യങ്ങളുടെ എണ്ണം കൂടാതെ “N” അറേയുടെ വലുപ്പം.

ഇതും കാണുക
ഒരു ബൈനറി ട്രീയുടെ ശരിയായ കാഴ്ച അച്ചടിക്കുക

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയുടെ വലുപ്പം.

അവലംബം