如何将数组区间内的所有值增加给定数量

Question

假设我有一个长度为L的数组A。我将获得n个区间(i,j)，并且我必须增加A[i]和A[j]之间的所有值。哪种数据结构最适合进行这些操作？
这些区间事先已知。

答案：线段树（Segment Tree）

- SHB

---

取决于。您计划支持哪些其他操作？ - Dennis Meng

我需要数组A的最终值。 - SHB

所以，您的意思是希望能够存储一个元素数组，并能够 1）将范围内的所有元素增加该值并且 2）查询数组中任何元素的值？ - Dennis Meng

@user2094963 好的。我会提供两种不同的方法；您可以选择适合您使用情况的方法。 - Dennis Meng

@TedHopp 是的，时间间隔可以重叠，并且我想在重叠区域内多次递增。 - SHB

Answer 1

你可以获得O(N + M)的时间复杂度。保持一个额外的增量数组B，其大小与A相同，最初为空（填充为0）。如果你需要将区间（i，j）增加值k，则执行B[i] += k和B[j + 1] -= k。

现在对B进行部分求和变换，考虑从0开始进行索引：

for (int i = 1; i < N; ++i) B[i] += B[i - 1];

现在A的最终值为A[i]+B[i]

- adrian.budau

---

太棒了的解决方案！只有一个建议，在创建B数组时，如果j+1 < ArrayBounds，则B[j+1] -= k，否则不要采取任何行动。 - Deepankar Singh

太棒了...顺便问一下，这个解决方案背后的直觉是什么？此外，我们是否有一个正式的名称来描述这种方法。 - Neeraj Jain

对于未来寻找此方法名称的读者，它被称为差分数组。 - deadLock

Answer 2

将所有间隔分为开始和结束索引：s_i，e_i是第i个间隔的起始索引（包括s_i）和结束索引（不包括e_i）

将所有s_i按照数组S排序 将所有e_i按照数组E排序

将increment设置为零， 开始线性扫描输入并将增量添加到每个人身上， 在每次循环中，如果下一个s_i是当前index，则增加increment， 如果下一个e_i是index，则减少increment

inc=0
s=<PriorityQueue of interval startindexes>
e=<PriorityQueue of interval endindexes>
for(i=0;i<n;i++){
  if( inc == 0 ){
    // skip adding zeros
    i=min(s.peek(),e.peek())
  }
  while( s.peek() == i ) {
    s.pop();
    inc++;
  }
  while( e.peek() == i ) {
    e.pop();
    inc--;
  }
  a[i]+=inc;
}

复杂度（不跳过非递增元素）：O(n+m*log(m)) // 这里的m是区间的数量 如果n>>m，那么复杂度为O(n)

跳过元素后的复杂度：O(min(n, \sum length(I_i)))，其中length(I_i)=e_i-s_i

- Zoltán Haindrich

---

如果您事先不知道间隔是什么怎么办？ - Dennis Meng

如果我理解问题正确，区间是作为输入或输入块给出的。 - Zoltán Haindrich

每个起始排序难道不都是O(NlnN)吗？ - Jiminion

我使用了优先队列，因为这样更容易理解...在实现中，我会使用排序索引数组。 - Zoltán Haindrich

对于不重叠的序列，\sum length(I_i) 不可能超过 n（除非区间存在越界索引）。对 n 的依赖应该消失。 - Ted Hopp

Answer 3

我可以想到三种主要方法：

方法1

这是最简单的方法，您只需保留数组不变，并对增量执行朴素操作。

• 优点：查询时间为常数
• 缺点：增量可能是线性时间（如果L很大，则速度相当慢）

方法2

这个方法有点复杂，但如果您计划经常增加，则更好。

将元素存储在二叉树中，使得中序遍历按顺序访问元素。每个节点（除了正常的左右子节点之外）还存储一个额外的int addOn，它将在“查询此树中的任何节点”时添加。

对于查询元素，请在索引上执行正常的二进制搜索，同时将所有addOn变量的值相加。将它们添加到您想要的节点的A[i]中，这就是您的值。

对于增量，进入树中进行遍历，根据需要更新所有这些新addOns。请注意，如果您将增量值加到一个节点的addOn中，则不会为两个子节点更新它。每个增量的运行时间为O(log L)，因为你只有在区间的第一个或最后一个元素在你的范围内时才必须“分支”。因此，您最多会分支2 log L次，并且在元素中访问更多的常数因子。

• 优点：增量现在的复杂度为O(log L)，因此如果您增加了大量增量，那么现在的速度比以前快得多。
• 缺点：查询需要更长时间（也是O(log L)），而且实现更加棘手。

方法3

使用区间树。

• 优点：和方法2一样，这种方法比朴素方法要快得多。
• 缺点：如果事先不知道区间是什么，就无法执行此操作。 另外，实现起来也很棘手。

- Dennis Meng

---

这个问题能用普通线段树解决吗？如果可以，怎么做？ - SHB

可能吧。我只是先想到这些。 - Dennis Meng

我觉得使用线段树来解决这个问题与第二种方法并没有太大的区别；将每个“addOn”视为对该子树中元素的一段/区间的对应。 - Dennis Meng

Answer 4

一个可能的O(M+N)算法实现，建议来自Adrian Budau。

import java.util.Scanner;

class Interval{
    int i;
    int j;
}

public class IncrementArray {
    public static void main(String[] args) {
        int k= 5;                                   // increase array elements by this value
        Scanner sc = new Scanner(System.in);
        int intervalNo = sc.nextInt();                // specify no of intervals
        Interval[] interval = new Interval[intervalNo];           // array containing ranges/intervals
        System.out.println(">"+sc.nextLine()+"<");
        for(int i=0;i<intervalNo;i++)
        {
            interval[i]= new Interval();
            String s = sc.nextLine();                             // specify i and j separated by comma in one line for an interval.
            String[] s1 = s.split(" ");
            interval[i].i= Integer.parseInt(s1[0]);
            interval[i].j= Integer.parseInt(s1[1]);
        }
        int[] arr = new int[10];           // array whose values need to be incremented.
        for(int i=0;i<arr.length;++i)
            arr[i]=i+1;                    // initialising array.
        int[] temp = new int[10];
        Interval run=interval[0]; int i;
        for(i=0;i<intervalNo;i++,run=interval[i<intervalNo?i:0] )  // i<intervalNo?i:0 is used just to avoid arrayBound Exceptions at last iteration.
        {
            temp[run.i]+=k;
            if(run.j+1<10)                                          // incrementing temp within array bounds.
            temp[run.j +1]-=k;
        }
        for (i = 1; i < 10; ++i) 
            temp[i] += temp[i - 1];

        for(i=0, run=interval[i];i<10;i++)
            {
                arr[i]+= temp[i];
                System.out.print(" "+arr[i]);                     // printing results.
            }


    }
}

- Deepankar Singh

Answer 5

解决单个区间的问题。然后迭代所有区间，并为每个区间应用单个区间的解决方案。最佳数据结构取决于语言。以下是Java示例：

public class Interval {
    int i;
    int j;
}

public void increment(int[] array, Interval interval) {
    for (int i = interval.i; i < interval.j; ++i) {
        ++array[i];
    }
}

public void increment(int[] array, Interval[] intervals) {
    for (Interval interval : intervals) {
        increment(array, interval);
    }
}

显然，如果你想减少代码量，你可以将一个循环嵌套在另一个循环中。然而，单区间方法本身可能是有用的。

编辑

如果区间事先已知，则可以稍微改进一下。您可以修改Interval结构以维护增量（默认为1）。然后按以下方式预处理区间集合S：

1. 将第二组区间T初始化为空集
2. 对于S中的每个区间I：如果I不与T中的任何区间重叠，则将I添加到T中；否则：
3. 对于T中与I重叠的每个区间J，从T中删除J，从I和J中形成新的区间K1...Kn（n可以从1到3），使它们之间没有重叠，并将K1...Kn添加到T中

完成后，使用T中的区间与早期代码（按描述进行修改）一起使用。由于没有重叠，数组的任何元素都不会被增加多次。对于固定的区间集，这是一个常数时间算法，无论数组长度如何。

对于N个区间，分割过程可以通过保持按区间起始索引排序的T来设计运行时间接近O(N log N)。但是，如果成本在许多数组增量操作中分摊，那么这对于总体复杂度并不是非常重要。

- Ted Hopp

---

我希望复杂度远小于O(LN)，其中L是数组的长度，N是区间的数量。 - SHB

@Jim - 一系列增量正是我建议的。然而，复杂度不是O（L + N）。考虑：如果一个区间长度为M（M = j-i），则需要M个增量操作；除非有一些硬件支持并行处理，否则无法避免这种情况，但我假设我们使用的是SISD机器。对于N个区间，复杂度将是O（MN）。我不明白L（数组的长度）如何进入方程式。 - Ted Hopp

@Jim - 你如何将非相邻的区间组合成组并获得任何效率？ - Ted Hopp

@Ted 假设你有N个长度为M的间隔（为简单起见），因此增量的总数将是N*M。将一对组合在一起需要2M。将它们分组成两个，有ln N个配对，因此总计是O(MlnN)（不像我之前说的）。我假设val += count与val++的成本相同。 - Jiminion

@Ted 我在想你仍然有M个元素，只是有些可能具有大于1的值。[从区间到数组的转换可能会更加耗时，尽管在理论上不是这样的情况。] - Jiminion