带有o(1)的数组 [英] array with o(1)

问题描述

我正在尝试以o(1)复杂度找到2D数组中随机子集的总和，大小最大为array [1000] [1000]，但让[4] [4]作为一个基本示例:

  array [4] [4] = {0，1，2，34、5、6、78、9、10、1112、13、14、15} 

我已经看到了一些一维数组的实现，您可以在其中存储运行总和，然后减去.

这是有道理的，但可以说我想要o(1)中 array [2] [2] 的总和为 array [3] [3] .这样就等于10 + 11 + 14 + 15.

但是如何在o(1)中完成呢?o(n)很简单.

与哈希表或更复杂的预处理数组有关吗?

编辑>>>

对于那些回到这个问题的人，只需添加一些注释:

1. 在谷歌搜索时有用的特定措辞似乎是求和区域表"或整体图像"或"Viola-Jones对象检测框架"
2. 有用的参考资料包括

   I am trying to find the sum of a random subset in a 2D array in o(1) complexity, size up to array[1000][1000] but lets take [4][4] as a basic example:

   array[4][4] = {0, 1, 2 ,3
                 4, 5, 6, 7
                 8, 9, 10, 11
                 12, 13, 14, 15}
   

   I have seen some implementations for 1 dimensional arrays where you store the running sum and then just subtract.

   That makes sense but lets say I want the sum of array[2][2] to array[3][3] in o(1). So it'd be 10 + 11 + 14 + 15.

   But how can this be done in o(1)? o(n) is easy.

   Is it something to do with hash tables or a more complicated pre-processed array?

   edit>>>

   Just some additioanl notes for anyone who comes back to this question:

   1. The specific wording that is useful when googling this seems to be 'summed-area table' or 'integral image' or 'Viola–Jones object detection framework'
   2. Useful references include https://computersciencesource.wordpress.com/2010/09/03/computer-vision-the-integral-image/ and https://en.wikipedia.org/wiki/Viola%E2%80%93Jones_object_detection_framework and https://en.wikipedia.org/wiki/Summed-area_table

   解决方案

   For each element [i][j], precompute the sum of all elements in the rectangle spanning from array[0][0] to array[i][j]; denote this value sums[i][j]. Then, to compute the sum of a rectangular subset i1 <= i <= i2 and j1 <= j <= j2, compute:

   sums[i2][j2] 
   - (i1 == 0 ? 0 : sums[i1 - 1][j2]) 
   - (j1 == 0 ? 0 : sums[i2][j1 - 1]) 
   + ((i1 == 0 || j1 == 0) ? 0 : sums[i1-1][j1-1])
   

   The bounds checks are used to avoid an illegal access outside of array bounds when the region of interest includes i==0 or j==0.

   As a rough geometric argument, see the below figure. To get the sum in the black rectangle, get the orange rectangle, subtract the red and green ones, and add back the purple one (since it got double-subtracted).

   这篇关于带有o(1)的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！