差异数组| O(1)中的范围更新查询  


难度级别
经常问 弓箭 编码国家 指令 Expedia的 谷歌 高通公司
排列 查询问题

给你一个 整数 排列 两种查询,一种是在范围内添加给定的数字,另一种是打印整个数组。 问题“差异数组| O(1)中的范围更新查询”要求我们在O(1)中执行范围更新。

使用案列  

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

说明

10将添加到20和30,因此该数组将变为{30,40,25,50}

然后,我们将打印整个数组。

将20加到30、40和25,因此数组将变为{50,60,45,50}

10将添加到45和50,因此该数组将变为{50,60,75,80}

然后,我们将再次打印整个数组。

执行查询后,将打印两组值。

差异数组| O(1)中的范围更新查询Pin

 

差分数组算法  

  1. 创建一个与给定数组大小相同的数组。
  2. 将第一个索引初始化为给定数组的第一个元素,将最后一个索引初始化为0。所有其他索引都填充有当前元素和上一个元素的差。
  3. 对于每个更新查询,将值X添加到创建的数组的给定左索引中,然后从创建的数组的右索引中减去X。
  4. 对于每个打印查询,首先我们使用公式A [i] = D [i] + A [i-1]填充输入数组。 然后打印值。
参见
给定两个未排序的数组,找到所有总和为x的对

说明  

给定一个数组和一个数字以及两种查询类型。 因此,我们必须执行两种类型的查询。 我们将有两个数字代表一个范围以及一个数字X。因此,我们的任务是将数字X添加到给定范围之间的所有索引中。 其中一种方法可能是使用幼稚的方法。 为此,每当需要更新值时,遍历给定的数组。

这里讨论一个更好的解决方案,即创建一个额外的数组来存储差异。 这就是为什么它被称为差异数组的原因。 首先,将差异数组的第一个元素初始化为输入数组的第一个元素。 然后将差异数组的最后一个元素分配为0。之后,我们将遍历该数组并将当前值和先前值的差异存储在差异数组中的当前索引处。

如果获得更新查询,我们将获得这些值作为范围。 除了我们,我们还提供了一些号码。 然后,我们将在差值数组的范围的左索引处添加该数字。 类似地,从差数组的右索引中减去值X。 为了打印数组,我们将遍历该数组,对于零索引值,我们将更新给定数组的值作为创建的数组,否则我们将获取创建的数组与给定数组的先前值的和。打印特定索引的值。

参见
给定范围内具有相等元素的索引数

代码  

C ++中差异数组的实现

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

Java中差异数组的实现

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

复杂度分析  

时间复杂度

O(q) 哪里 “Q” 是更新查询执行时执行的打印查询的数量 O(1) 时间。

参见
具有不同元素的子数组

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 由于我们创建了一个额外的差分数组,因此我们具有线性的空间复杂度。