이진 배열에서 쿼리 계산 및 전환

난이도 하드
자주 묻는 질문 아마존 Facebook 구글 동네 짱
배열 세그먼트 트리조회수 34

An 정렬 크기 n의 입력 값으로 제공되었습니다. "이진 배열에서 쿼리 개수 및 토글"문제는 아래에 제공된 쿼리 중 일부를 수행하도록 요청하며 쿼리는 임의의 방식으로 달라질 수 있습니다.

문의는 ⇒

토글 쿼리 ⇒ 토글 (시작, 종료),이 토글 쿼리는 주어진 범위 내에서 0을 1로 또는 1을 0으로 변경하는 것을 의미합니다.

Count query ⇒ count (starting, ending),이 count query는 주어진 범위 내의 모든 개수를 세는 것을 의미합니다.

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. Boolean이 부울 트리 참 또는 거짓입니다. 참이면 해당 노드를 거짓으로 표시하십시오. 값 업데이트 세그먼트 트리 끝으로 – 시작 + 1 segmentTree [노드].
  2. 리프 노드가 아닌지 확인한 다음 값을 설정하거나 반전합니다. 부울 트리 아이들의
  3. 값이 범위를 벗어나면 반환합니다.
  4. 확인 세그먼트 트리 범위 내에 들어 오면 true 인 경우 segmentTree의 현재 요소 값을 차이로 업데이트하고 리프 노드가 아닌지 다시 확인하고 2 단계와 동일한 절차를 수행합니다.
  5. segmentTree가 범위 내에 있지 않고 값이 segmentTree의 양쪽에서 겹치는 지 확인한 다음 재귀 호출을 수행하십시오.
  6. segmentTree 노드의 현재 노드 값을 자식 결과로 업데이트합니다.

카운트 쿼리

  1. 현재 노드가 범위를 벗어 났는지 확인한 다음 0을 반환합니다.
  2. 그런 다음 boolTrees의 현재 노드가 참인지 확인하고 참이면 boolTrees의 현재 노드를 거짓으로 표시하고 segmentTree의 현재 노드 값을 차이로 업데이트합니다.
  3. 리프 노드가 아닌지 확인하고 자식 값을 반전합니다.
  4. segmentTree가 주어진 범위에 있는지 확인한 다음 segmentTree [node]를 반환합니다.
  5. 그렇지 않은 경우 겹치지 않도록 함수를 재귀 적으로 호출합니다.

설명

모든 값이 0으로 초기화되도록 n의 배열을 제공했습니다. 주어진 범위 내에서 모든 0을 1로, 모든 1을 0으로 반전시키는 토글 쿼리 인 두 개의 쿼리를 수행 할 것입니다. . 개수 쿼리는 주어진 범위 내에있는 모든 0을 계산하는 것입니다. 1으로 초기화 된 segmentTree를 사용할 것입니다. 따라서 범위 내에서 XNUMX로 변환합니다.

토글 함수가 호출 될 때마다, 우리는 boolTree로 생성 한 Boolean 배열을 찾고 false로 초기화되고 boolTree의 현재 노드 값이 참인지 거짓인지 확인할 것입니다. 거짓이면 업데이트에 지금까지 완료되지 않았습니다. 그래서 우리는 그것을 할 필요가 있습니다. 그리고 그것이 참이라면, 우선 그것을 거짓으로 표시하여 나중에 사용할 수 있도록하고, 종료와 시작의 차이의 합으로 현재 노드에서 segmentTree의 값을 업데이트합니다. 그리고 1과 현재 노드의 segmentTree 값의 차이. 리프 노드가 아닌지 확인할 것입니다. 왜냐하면 리프 노드가 아닌 경우 이후에는 작업을 수행하지 않기 때문입니다. 그렇지 않은 경우 하위 노드의 값을 부울 값으로 업데이트합니다.

segmentTree의 현재 세그먼트가 주어진 범위 내에 있는지 확인하십시오. 그렇지 않은 경우 노드 세그먼트가 주어진 범위 내에 있도록 재귀 호출을 수행하십시오.

같은 일이 count 함수와 관련되지만 약간 다른 접근 방식을 사용합니다. 우리는 현재 노드가 단순히 값 0을 반환하는 경우 범위를 벗어나서는 안되는지 확인합니다.

현재 노드가 segmentTree의 현재 노드로 표시되지 않아야하는지 확인합니다. true이면 현재 노드를 false로 업데이트하고 현재 노드의 segmentTree 값을 종료와 시작의 차이와 toggling 함수에서 수행 한 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" 쿼리 수이며 "엔" 배열의 크기입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 크기입니다.

참고

Translate »