algorithm - 跨度快速最小值

Question

给定一个数组列表和大量的设置时间，我需要快速找到每个数组的某些子跨度中的最小值。在概念上:

class SpanThing
{
     int Data;
     SpanThing(int[][] data) /// must be rectangulare
     {
         Data = data;
         //// process, can take a while
     }

     int[] MinsBruteForce(int from, int to)
     {
         int[] result = new int[data.length];
         foreach(int index, int[] dat; Data)
         {
             result[i] = int.max;
             foreach(int v; dat[from .. to]);
                result[i] = min(result[i], v);
         }
         return result;
     }
     int[] MinsSmart(int from, int to)
     {
          // same as MinsBruteForce but faster
     }
}

我目前关于如何做到这一点的想法是在数据上构建一个二叉树，其中每个节点都包含相关跨度中的最小值。这样，查找一行的跨度中的最小值将包括仅查找组成该行的树节点的最小值。该集合对于每一行都是相同的，因此可以计算一次。

有人认为这个想法有任何问题或知道更好的方法吗？

---

为了澄清，我正在讨论的树将被设置为根节点将包含整行的最小值，对于每个节点，它的左子节点将包含该行左半部分的最小值父级的跨度和右侧相同。

 0   5   6  2   7   9   4   1   7   2   8   4   2
 ------------------------------------------------
   | 5 | 6|   | 7 | 9 |   | 1 | 7 | 2 | 8 | 4 | 2  
 0 |   5  | 2 |   7   | 4 |   1   |   2   |   2  
   0      |   2       |   1       |       2
          0           |           1
                      0

该树可以映射到数组并以可以计算段边界的方式定义，从而实现快速查找。

我正在优化的情况是，我有一个固定的输入集和大量的前期时间，但随后需要对各种跨度进行许多快速测试。

Answer 1

您提出的解决方案似乎使用恒定的空间开销、恒定的时间设置和查询的对数时间来给出答案。如果您愿意支付二次空间(即提前计算所有间隔)，您可以在恒定时间内得到答案。您的对数方案几乎肯定是首选。

如果可以做得更好，我不会感到惊讶，但如果有一个简单数据结构可以做得更好，而且在实践中，对数时间，我会感到震惊几乎总是足够快。努力吧。