分段树中的延迟传播

本文介绍了分段树 以前的职位 以区间和问题为例。我们使用了相同的“给定范围之和”问题来解释延迟传播

在简单段树中更新是如何工作的？ 在 以前的职位 ，调用update函数仅更新数组中的单个值。请注意，数组中的单个值更新可能会导致段树中的多个更新，因为可能有许多段树节点的范围中有单个数组元素。 下面是前一篇文章中使用的简单逻辑。 1） 从段树的根开始。 2） 如果要更新的数组索引不在当前节点的范围内，则返回 3） 否则，更新当前节点并为子节点重复。 以下代码取自上一篇文章。

如果一系列数组索引都有更新怎么办？ 例如，将10添加到数组中从2到7的所有索引值中。必须为2到7之间的每个索引调用上述更新。我们可以通过编写相应更新节点的函数updateRange（）来避免多次调用。

延迟传播–一种优化，可使范围更新更快 当有很多更新并且在某个范围内进行了更新时，我们可以推迟一些更新（避免更新中的递归调用），并且只在需要时进行这些更新。 请记住，段树中的节点存储或表示一系列索引的查询结果。如果该节点的范围在更新操作范围内，则该节点的所有子节点也必须更新。例如，在上面的图中考虑值为27的节点，这个节点将索引的值和存储在3到5之间。如果我们的更新查询的范围是2到5，那么我们需要更新这个节点和这个节点的所有后代。通过延迟传播，我们只更新值为27的节点，并将更新信息存储在称为延迟节点或值的单独节点中，从而推迟对其子节点的更新。我们创建了一个代表懒惰节点的数组lazy[]。lazy[]的大小和表示段树的数组相同，在下面的代码中是tree[]。 其思想是将lazy[]的所有元素初始化为0。lazy[i]中的值0表示在段树中的节点i上没有挂起的更新。lazy[i]的非零值意味着在对节点进行任何查询之前，需要将该值添加到段树中的节点i。 下面是修改后的更新方法。

// To update segment tree for change in array// values at array indexes from us to ue.updateRange(us, ue)1) If current segment tree node has any pending   update, then first add that pending update to   current node.2) If current node's range lies completely in    update query range.....a) Update current node....b) Postpone updates to children by setting        lazy value for children nodes.3) If current node's range overlaps with update    range, follow the same approach as above simple   update....a) Recur for left and right children....b) Update current node using results of left       and right calls.

查询功能也有什么变化吗？ 由于我们更改了更新以推迟其操作，因此如果对尚未更新的节点进行查询，可能会出现问题。所以我们也需要更新我们的查询方法 getSumUtil在之前的帖子中 。getSumUtil（）现在首先检查是否有挂起的更新，如果有，然后更新节点。一旦确保完成了挂起的更新，它的工作原理与之前的getSumUtil（）相同。 下面是演示惰性传播工作的程序。

C/C++

// Program to show segment tree to demonstrate lazy// propagation#include <stdio.h>#include <math.h>#define MAX 1000// Ideally, we should not use global variables and large// constant-sized arrays, we have done it here for simplicity.int tree[MAX] = {0};  // To store segment treeint lazy[MAX] = {0};  // To store pending updates/*  si -> index of current node in segment tree    ss and se -> Starting and ending indexes of elements for                 which current nodes stores sum.    us and ue -> starting and ending indexes of update query    diff -> which we need to add in the range us to ue */void updateRangeUtil(int si, int ss, int se, int us,                     int ue, int diff){    // If lazy value is non-zero for current node of segment    // tree, then there are some pending updates. So we need    // to make sure that the pending updates are done before    // making new updates. Because this value may be used by    // parent after recursive calls (See last line of this    // function)    if (lazy[si] != 0)    {        // Make pending updates using value stored in lazy        // nodes        tree[si] += (se-ss+1)*lazy[si];        // checking if it is not leaf node because if        // it is leaf node then we cannot go further        if (ss != se)        {            // We can postpone updating children we don't            // need their new values now.            // Since we are not yet updating children of si,            // we need to set lazy flags for the children            lazy[si*2 + 1]   += lazy[si];            lazy[si*2 + 2]   += lazy[si];        }        // Set the lazy value for current node as 0 as it        // has been updated        lazy[si] = 0;    }    // out of range    if (ss>se || ss>ue || se<us)        return ;    // Current segment is fully in range    if (ss>=us && se<=ue)    {        // Add the difference to current node        tree[si] += (se-ss+1)*diff;        // same logic for checking leaf node or not        if (ss != se)        {            // This is where we store values in lazy nodes,            // rather than updating the segment tree itself            // Since we don't need these updated values now            // we postpone updates by storing values in lazy[]            lazy[si*2 + 1]   += diff;            lazy[si*2 + 2]   += diff;        }        return;    }    // If not completely in rang, but overlaps, recur for    // children,    int mid = (ss+se)/2;    updateRangeUtil(si*2+1, ss, mid, us, ue, diff);    updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);    // And use the result of children calls to update this    // node    tree[si] = tree[si*2+1] + tree[si*2+2];}// Function to update a range of values in segment// tree/*  us and eu -> starting and ending indexes of update query    ue  -> ending index of update query    diff -> which we need to add in the range us to ue */void updateRange(int n, int us, int ue, int diff){   updateRangeUtil(0, 0, n-1, us, ue, diff);}/*  A recursive function to get the sum of values in given    range of the array. The following are parameters for    this function.    si --> Index of current node in the segment tree.           Initially 0 is passed as root is always at'           index 0    ss & se  --> Starting and ending indexes of the                 segment represented by current node,                 i.e., tree[si]    qs & qe  --> Starting and ending indexes of query                 range */int getSumUtil(int ss, int se, int qs, int qe, int si){    // If lazy flag is set for current node of segment tree,    // then there are some pending updates. So we need to    // make sure that the pending updates are done before    // processing the sub sum query    if (lazy[si] != 0)    {        // Make pending updates to this node. Note that this        // node represents sum of elements in arr[ss..se] and        // all these elements must be increased by lazy[si]        tree[si] += (se-ss+1)*lazy[si];        // checking if it is not leaf node because if        // it is leaf node then we cannot go further        if (ss != se)        {            // Since we are not yet updating children os si,            // we need to set lazy values for the children            lazy[si*2+1] += lazy[si];            lazy[si*2+2] += lazy[si];        }        // unset the lazy value for current node as it has        // been updated        lazy[si] = 0;    }    // Out of range    if (ss>se || ss>qe || se<qs)        return 0;    // At this point we are sure that pending lazy updates    // are done for current node. So we can return value     // (same as it was for query in our previous post)    // If this segment lies in range    if (ss>=qs && se<=qe)        return tree[si];    // If a part of this segment overlaps with the given    // range    int mid = (ss + se)/2;    return getSumUtil(ss, mid, qs, qe, 2*si+1) +           getSumUtil(mid+1, se, qs, qe, 2*si+2);}// Return sum of elements in range from index qs (query// start) to qe (query end).  It mainly uses getSumUtil()int getSum(int n, int qs, int qe){    // Check for erroneous input values    if (qs < 0 || qe > n-1 || qs > qe)    {        printf("Invalid Input");        return -1;    }    return getSumUtil(0, n-1, qs, qe, 0);}// A recursive function that constructs Segment Tree for//  array[ss..se]. si is index of current node in segment// tree st.void constructSTUtil(int arr[], int ss, int se, int si){    // out of range as ss can never be greater than se    if (ss > se)        return ;    // If there is one element in array, store it in    // current node of segment tree and return    if (ss == se)    {        tree[si] = arr[ss];        return;    }    // If there are more than one elements, then recur    // for left and right subtrees and store the sum    // of values in this node    int mid = (ss + se)/2;    constructSTUtil(arr, ss, mid, si*2+1);    constructSTUtil(arr, mid+1, se, si*2+2);    tree[si] = tree[si*2 + 1] + tree[si*2 + 2];}/* Function to construct segment tree from given array.   This function allocates memory for segment tree and   calls constructSTUtil() to fill the allocated memory */void constructST(int arr[], int n){    // Fill the allocated memory st    constructSTUtil(arr, 0, n-1, 0);}// Driver program to test above functionsint main(){    int arr[] = {1, 3, 5, 7, 9, 11};    int n = sizeof(arr)/sizeof(arr[0]);    // Build segment tree from given array    constructST(arr, n);    // Print sum of values in array from index 1 to 3    printf("Sum of values in given range = %d",           getSum(n, 1, 3));    // Add 10 to all nodes at indexes from 1 to 5.    updateRange(n, 1, 5, 10);    // Find sum after the value is updated    printf("Updated sum of values in given range = %d",            getSum( n, 1, 3));    return 0;}

输出：

Sum of values in given range = 15Updated sum of values in given range = 45 

本文由 安基特·米塔尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论