c++ - 带点更新的范围总和范围

Question

我们有一个数组 A，有 N 个元素和 N 个范围，每个范围都是 [L, R] 的形式。将范围的值称为 A 中从索引 L 到索引 R(含)的所有元素的总和。

示例:让数组 A = [2 5 7 9 8] 并且给定的范围是 [2,4] 那么这个范围的值是 5+7+9=21

现在我们有 Q 个查询，每个查询都是 2 种类型之一:

1. 0 X Y : It means change Xth element of array to Y.
2. 1 A B : It means we need to report the sum of values of ranges from A to B.

示例:让数组 A = [2 3 7 8 6 5] 并让我们有 3 个范围:

R1: [1,3] Then value corresponding to this range is 2+3+7=12
R2: [4,5] Then value corresponding to this range is 8+6=14
R3: [3,6] Then value corresponding to this range is 7+8+6+5=26

现在让我们有 3 个查询:

Q1: 1 1 2
Then here answer is value of Range1 + value of Range2 = 12+14=26 

Q2: 0 2 5
It means Change 2nd element to 5 from 3.It will change the result of Range 1.
Now value of Range1 becomes 2+5+7=14

Q3: 1 1 2
Then here answer is value of Range1 + value of Range2 = 14+14=28 

如果我们有 10^5 个查询并且 N 也达到 10^5，该怎么做。如何高效地向 Queries2 报告？

我的方法: 第一个查询很容易处理。我可以从数组构建一个线段树。我可以用它来计算第一个数组(第二个数组中的一个元素)中一个区间的总和。但是我如何处理 O(log n) 中的第二个查询？在最坏的情况下，我更新的元素将在第二个数组中的所有间隔中。

我需要一个 O(Qlog N) 或 O(Q(logN)^2) 的解决方案。

显然我们不能为每个查询设置 O(N)。所以请帮助获得有效的方法

我当前的代码:

#include<bits/stdc++.h>
using namespace std;
long long  arr[100002],i,n,Li[100002],Ri[100002],q,j;
long long  queries[100002][2],query_val[100002],F[100002],temp;
long long   ans[100002];
int main()
{
scanf("%lld",&n);
for(i=1;i<=n;i++)
    scanf("%lld",&arr[i]);
for(i=1;i<=n;i++)
{
    scanf("%lld%lld",&Li[i],&Ri[i]);
}
for(i=1;i<=n;i++)
{
    F[n] = 0;
    ans[i] = 0;
}
scanf("%lld",&q);
for(i=1;i<=q;i++)
{
    scanf("%lld",&query_val[i]);
    scanf("%lld%lld",&queries[i][0],&queries[i][1]);
}
for(i=1;i<=n;i++)
{
    for(j=Li[i];j<=Ri[i];j++)
    {
        F[i] = F[i] + arr[j];
    }
}
long long  diff;
long long  ans_count = 0,k=1;
for(i=1;i<=q;i++)
{
    if(query_val[i] == 1)
    {
        temp = arr[queries[i][0]];
        arr[queries[i][0]] = queries[i][1];
        diff =  arr[queries[i][0]] - temp;
        for(j=1;j<=n;j++)
        {
            if(queries[i][0]>=Li[j] && queries[i][0]<=Ri[j])
                F[j] = F[j] + diff;
            ++k;
        }

    }
    else if(query_val[i] == 2)
    {
        ++ans_count;
        for(j=queries[i][0];j<=queries[i][1];j++)
            ans[ans_count] = ans[ans_count] + F[j];

    }
}
for(i=1;i<=ans_count;i++)
{
    printf("%lld\n",ans[i]);
}
return 0;
}

虽然代码是正确的，但是对于更大的测试用例，它需要很长时间。请帮助

Answer 1

#include <iostream>
using namespace std;
typedef long long ll;
void updateSegementLazyTree(ll *tree , ll *lazy , ll low, ll high,ll startR ,ll endR ,ll updateValue ,ll treeNode)
{

    //before using current node we need to check weather currentnode has any painding updation or not
    if (lazy[treeNode]!=0)
    {
        //update painding updation
        tree[treeNode]  +=  (high-low+1)*lazy[treeNode];
        //transfer update record to child of current node if child possible
        if (low!=high)
        {
            //that's means child possible
            lazy[treeNode*2]    += lazy[treeNode];  //append update to left child
            lazy[treeNode*2+1]  += lazy[treeNode];  //append update to right child
        }
        lazy[treeNode]=0;//remove lazyness of current node
    }
    //if our current interval [low,high] is completely outside of the given Interval[startR,endR]
    if (startR >high || endR <low || low>high)
    {   
        //then we have to ignore those path of tree
        return;
    }
    //if our current interval is completely inside of given interval
    if (low >=startR && high <=endR)
    {
        //first need to update the current node with their painding updation
        tree[treeNode]  += (high-low+1)*updateValue;
        if (low!=high)
        {
            //that's means we are at the non-leaf node
            lazy[treeNode*2] +=updateValue; //so append lazyness to their left child
            lazy[treeNode*2+1] +=updateValue;//append lazyness to their right child
        }
        return;
    }
    //partially inside and outside then we have to traverse all sub tree i.e. right subtree and left subtree also
    ll mid=(low+high)/2;
    updateSegementLazyTree(tree ,  lazy ,  low,  mid, startR , endR , updateValue , treeNode*2);
    updateSegementLazyTree(tree ,  lazy ,  mid+1,  high, startR , endR , updateValue , treeNode*2+1);

    //while poping the function from stack ,we are going to save what i have done....Ok!!!!
    //update tree node:-
    tree[treeNode]  = tree[treeNode*2] + tree[treeNode*2+1];    //left sum+rightsum(after updation)
}
ll getAnswer(ll *tree ,ll * lazy , ll low, ll high ,ll startR,ll endR , ll treeNode)
{
    //base case
    if (low>high)
    {
        return 0;
    }
    //completely outside
    if (low >endR || high <startR)
    {
        return 0;
    }
    //before using current node we need to check weather currentnode has any painding updation or not
    if (lazy[treeNode]!=0)
        {
            //i.e. if we would have added x value from low to high then total changes for root node will be (high-low+1)*x
            tree[treeNode]  += (high-low+1)*lazy[treeNode];
            if (low!=high)
            {
                //if we are at non-leaf node
                lazy[treeNode*2] += lazy[treeNode]; //append updateion process to left tree
                lazy[treeNode*2+1] += lazy[treeNode];//append updation process to right tree
            }
            lazy[treeNode]=0;
        }
    //if our current interval is completely inside of given interval
    if (low >=startR && high <=endR)
    {
        return tree[treeNode];
    }
    //if our current interval is cpartially inside and partially out side of given interval then we need to travers both side left and right too
    ll mid=(low+high)/2;
    if(startR>mid)
    {
        //that's means our start is away from mid so we need to treverse in right subtree
        return getAnswer( tree ,  lazy ,  mid+1, high, startR, endR ,  treeNode*2+1);
    }else if(endR <= mid){
        //that's means our end is so far to mid or equal so need to travers in left subtree
        return getAnswer( tree ,  lazy ,  low, mid, startR, endR ,  treeNode*2);
    }
    ll left=getAnswer( tree ,  lazy ,  low, mid, startR, endR ,  treeNode*2);   //traverse right
    ll right=getAnswer( tree ,  lazy ,  mid+1, high, startR, endR ,  treeNode*2+1); //and left
    return (left+right);//for any node total sum=(leftTreeSum+rightTreeSum)
}
int main()
{
    int nTestCase;
    cin>>nTestCase;
    while(nTestCase--)
    {
        ll n,nQuery;
        cin>>n>>nQuery;
        ll *tree=new ll[3*n]();
        ll *lazy=new ll[3*n]();
        while(nQuery--)
        {
            int choice;
            cin>>choice;
            if (choice==0)
            {
                ll startR,endR,updateValue;
                cin>>startR>>endR>>updateValue;
                //0:- start index , n-1 end index ,1 treeIndex tree is our segment tree and lazy is our lazy segment tree
                updateSegementLazyTree(tree , lazy , 0, n-1, startR-1 , endR-1 , updateValue , 1);
            // for (int i = 0; i < 3*n; ++i)
            //  {
            //      cout<<i<<"\t"<<tree[i]<<"\t"<<lazy[i]<<endl;
            //  }
            }else{
                ll startR,endR;
                cin>>startR>>endR;
                ll answer=getAnswer(tree , lazy , 0, n-1 , startR-1 , endR-1 , 1);
                cout<<answer<<endl;
            }
        }
    }
}

updateSegementLazyTree() 采用两个大小为 4*n 的数组，因为长度为 log(n) 的可能节点总数将是 2*2^log(n)，最多是 4*n。然后我们还需要interval[startR,endr]和updateValue，我们通过recrusion维护。 Tree[treeNode] 表示左右所有元素的和。

示例输入如下:

1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8

因此对于第一个查询，我们必须将 2-4 更新为 +26。我们没有更新 2-4 之间的所有元素，而是将其存储在惰性树中，每当我们访问树中的任何节点时，我们首先检查该节点是否有任何待处理的更新。如果没有待处理的更新，请完成并将其转移给他们的 child 。

q1:- 0 2 4 26
tree[0,78,78,0,26,52,0,0,0,26] 

尝试做树索引；对于左 tree(2*i+1) 和 right(2*i+1)第一个索引至少为 78，即树的顶部，因此从 [0,n-1] 当前最大值为 78。

tree[treeNode] += (high-low+1)*lazy[treeNode];

如果我们从低索引到高添加 x 那么在整个子数组 i 中添加了 (high-low+1)*x ； -1 因为从 0 开始索引。

然后，在访问树中的任何节点之前，我们懒惰地检查该节点是否有任何待处理的更新。 if (lazy[treeNode]!=0) 如果有，则更新并将 lazy 传递给他们的 child 。对左子树和右子树也继续这样做。

然后我们在 range[startR,endR] 内到达 getAnswer()正如我之前提到的，我们首先检查每个受影响节点的挂起更新。如果为真则它完成该更新并根据间隔递归调用左右子树。

最后我们得到根节点的leftSubtree和rightsubtree的和，将它们相加并返回。

时间复杂度

在更新中，getAnswer()，在最坏的情况下必须遍历整棵树，即树的高度 O(2*Log N)。 2*log n 因为这是最坏的情况，我们必须在左右子树中移动，例如对于区间 [0-n-1]。

对于 k 查询，整体时间复杂度为 O(K*log n)。