假设我有一个长度为 L 的数组 A。我将获得 n 个区间 (i,j)，并且我必须递增 A[i] 和 A[j] 之间的所有值。哪种数据结构最适合给定的操作?
间隔是预先知道的。
问问题
15112 次
5 回答
19
你可以得到 O(N + M)。保持一个与 A 相同大小的额外增量数组 B 最初为空（填充为 0）。如果您需要使用值 k 增加范围 (i, j)，则执行 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]
于 2013-08-23T19:14:25.060 回答
8
将所有间隔分解为开始和结束索引：s_i，对于开始包括和结束不e_i包括的第 i 个间隔s_ie_i
将所有s_i-s 排序为数组 S 将所有e_i-s 排序为数组 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
于 2013-08-23T18:04:39.390 回答
3
我能想到的主要方法有以下三种：
方法一
这是最简单的一种，你只需保持数组不变，然后做一些简单的事情来增加。
- 优点：查询是固定时间
- 缺点：增量可以是线性时间（如果 L 很大，因此会很慢）
方法二
这个有点复杂，但如果你打算增加很多，那就更好了。
将元素存储在二叉树中，以便按顺序遍历按顺序访问元素。每个节点（除了正常的左右子子节点外）还存储一个额外的int addOn，它将是“当您查询此树中的任何节点时添加我”。
对于查询元素，对索引进行正常的二进制搜索以查找元素，同时将addOn变量的所有值相加。将它们添加到A[i]您想要的节点上，这就是您的价值。
对于增量，向下遍历树，addOns根据需要更新所有这些新的。请注意，如果将增量值添加到addOn一个节点，则不会为两个子节点更新它。每个增量的运行时间是 then O(log L)，因为您唯一需要“分支”到子项的时间是区间中的第一个或最后一个元素在您的范围内时。因此，您在大多数时候都会分支2 log L，并在元素中更多地访问常数因子。
- 优点：增量现在是 O(log L)，所以如果你增加一吨，现在事情会比以前快得多。
- 缺点：查询需要更长的时间（也是 O(log L)），并且实现起来要复杂得多。
方法 3
使用区间树。
- 优点：就像方法 2 一样，这个方法比简单的方法快得多
- 缺点：
如果您事先不知道间隔将是多少，则不可行。
实施起来也很棘手
于 2013-08-23T18:00:53.203 回答
0
解决单个区间的问题。然后遍历所有区间并为每个区间应用单区间解。最好的数据结构取决于语言。这是一个 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进行如下预处理：
- 将第二组区间T初始化为空集
- 对于S中的每个区间I：如果 I 不与 T 中的任何区间重叠，则将I添加到T；否则：
- 对于T中与I重叠的每个区间J，从T中删除J ，从I和J中形成新的区间K 1 ... K n ，使得没有重叠（n可以从 1 到 3），然后添加K 1。 .. K n到T
完成后，将T中的间隔与早期代码一起使用（如所述修改）。由于没有重叠，因此数组的任何元素都不会增加一次以上。对于一组固定的间隔，这是一个恒定时间算法，与数组长度无关。
对于 N 个区间，分裂过程可能被设计为在接近 O(N log N) 的情况下运行，方法是保持T按区间开始索引排序。但是，如果成本在许多数组增量操作中分摊，这对整体复杂性来说并不是那么重要。
于 2013-08-23T17:47:22.127 回答
0
Adrian Budau建议的 O(M+N) 算法的可能实现
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.
}
}
}
于 2016-06-15T14:17:35.200 回答