2D线段树更新/修改步骤复杂度

Question

我对在https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/的“修改查询”复杂度有些困惑。该文章底部指出其复杂度为O(2 * n * log n * log m)。为什么不只是O(log n * log m)? 额外的线性项n从哪里来？

- user5965026

Answer 1

检查他们的更新实现。

def update(pos, low, high, x, y, val): 
  
    if (low == high) : 
        finalUpdate(1, 1, 4, x, val, pos) 
      
    else : 
        mid = (low + high) // 2
  
        if (low <= y and y <= mid) : 
            update(2 * pos, low, mid, x, y, val) 
  
        else : 
            update(2 * pos + 1, mid + 1,  
                       high, x, y, val) 
  
        for i in range(1, size): 
            fin_seg[pos][i] = (fin_seg[2 * pos][i] +
                               fin_seg[2 * pos + 1][i]) 

请注意，在组合步骤结束时，它正在迭代数组的所有列并更新相应树的所有项目。这就是 n 来源的地方。但我会说复杂度为 O(n * log(m) + log(n)，因为最终的更新仅调用一次且只进行了 log(n) 次更改。

没有 n 因素的实现

只重新计算依赖于更改元素的节点的实现复杂度为 O(log(n)*log(m))。这可以通过在 finalUpdate 中跟踪更改的元素来实现。

def finalUpdate(pos, low, high, x, val, node): 
    if (low == high) : 
        fin_seg[node][pos] = val 
        return [pos]
    else : 
        mid = (low + high) // 2
  
        if (low <= x and x <= mid) : 
            changes = finalUpdate(2 * pos, low, mid,  
                            x, val, node) 
          
        else : 
            changes = finalUpdate(2 * pos + 1, mid + 1,  
                            high, x, val, node) 
  
        changes.append(pos);
        fin_seg[node][pos] = (fin_seg[node][2 * pos] + 
                              fin_seg[node][2 * pos + 1]) 
        return changes

finalUpdate 是二分查找，因此它将被称为 log(m) 递归，每次调用都会更改一个元素，因此更改的次数将是 log(m)。

def update(pos, low, high, x, y, val): 
  
    if (low == high) : 
        changes = finalUpdate(1, 1, 4, x, val, pos) 
      
    else : 
        mid = (low + high) // 2
  
        if (low <= y and y <= mid) : 
            changes = update(2 * pos, low, mid, x, y, val) 
  
        else : 
            changes = update(2 * pos + 1, mid + 1,  
                       high, x, y, val) 
  
        for i in changes: 
            fin_seg[pos][i] = (fin_seg[2 * pos][i] +
                               fin_seg[2 * pos + 1][i]) 
    return changes;

更新将进行二分查找，将被称为log(n)次，每次调用将重新计算log(m)个节点。

- Bob

---

啊，我没看到那个for循环。是的，我认为这个循环是无意义的。虽然有了这个循环，但我认为复杂度应该是O(n log m + log n) = O(n log m)。 - user5965026

啊，你说得对，我可能把 m 和 n 搞混了。 - Bob

@user5965026 这篇帖子回答了你的问题吗？如果没有，那么缺少什么呢？ - Anatolii