計數和切換二進制數組上的查詢


難度級別
經常問 亞馬遜 Facebook 谷歌 尤伯杯
排列 段樹

An 排列 已將大小為n的n作為輸入值。 問題“二進制數組上的計數和切換查詢”要求執行下面給出的某些查詢,查詢可以隨機方式變化。

查詢是⇒

切換查詢⇒切換(開始,結束),此切換查詢表示在給定範圍內將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. 檢查布爾值 布爾樹 是對還是錯。 如果為true,則將該節點標記為false。 更新中的值 段樹 作為結束–起始+ 1 segmentTree [node]。
  2. 檢查它是否不是葉節點,然後設置或反轉其值 布爾樹 孩子的。
  3. 如果值超出範圍,則返回。
  4. 檢查是否 段樹 進入範圍,如果為true,則更新segmentTree的當前元素值作為差異,並再次檢查它是否不是葉節點,並執行與步驟2中相同的過程。
  5. 檢查segmentTree是否不在範圍內,並且值在segmentTree的任一側都重疊,然後進行遞歸調用。
  6. 作為其子級結果,更新segmentTree節點的當前節點的值。

計數查詢

  1. 檢查當前節點是否超出範圍,然後返回0。
  2. 然後查看boolTrees的當前節點是否為true,如果為true,則將boolTrees的當前節點標記為false並更新segmentTree的當前節點值作為差異。
  3. 檢查它是否不是葉節點,然後反轉子節點的值。
  4. 檢查segmentTree是否在給定範圍內,然後返回segmentTree [node]。
  5. 如果不是,則遞歸調用該函數,以使其不重疊。

解釋

我們給定了一個n數組,以便將其所有值初始化為0。我們將執行給定的兩個查詢,即切換查詢,這將在給定範圍內將所有0轉換為1,並將所有1轉換為0。 。 計數查詢是對給定範圍內存在的所有零進行計數。 我們將使用被初始化為0的segmentTree。因此,我們將其轉換為範圍內的1s。

每當調用toggle函數時,我們都會查找我們創建為boolTree且初始化為false的布爾數組,我們將檢查boolTree的當前節點值是true還是false,如果為false則意味著任何更新都具有直到現在還沒有完成。 因此,我們需要這樣做,如果它為true,則首先將其標記為false,以便稍後使用,並將當前節點處segmentTree的值更新為結束和開始之差的總和以及1與segmentTree的當前節點值之差。 我們將檢查它是否不是葉節點,因為如果是,則此後我們將不進行任何操作。 如果不是,則我們將子節點的值更新為布爾值。

檢查segmentTree的當前段是否在給定範圍內。 如果不是,則進行遞歸調用,以使節點段在給定範圍內。

計數功能是一回事,但方法稍有不同。 我們將檢查當前節點是否應該超出範圍,如果它隨後僅返回值0。

檢查當前節點是否不應該用segmentTree的當前節點標記。 如果為true,則將當前節點更新為false,並將segmentTree的當前節點的值更新為我們在切換功能中完成的結束和開始之差與segementTree的當前節點和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” 是數組的大小。

參考文獻