计数和切换二进制数组上的查询


难度级别
经常问 亚马逊 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” 是数组的大小。

参考