#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节点的总数 最多为。然后我们还需要并且我们通过recrution来维护。表示左右所有元素的总和。log(n)2*2^log(n)4*ninterval[startR,endr]updateValueTree[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 之间的所有元素，而是将其存储在惰性树中，每当我们从树中访问任何节点时，我们首先检查该节点是否有任何待处理的更新。如果没有待处理的更新，则完成并将其转移给他们的孩子。
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)如果有，则更新并懒惰地转移给他们的孩子。对左子树和右子树也继续这样做。
然后我们到达getAnswer()内部range[startR,endR]
正如我之前提到的，我们首先检查每个受影响节点的待处理更新。如果为真，则完成更新并根据间隔递归调用左右子树。
最后我们得到根节点的总和leftSubtree和总和，将它们相加并返回。rightsubtree
时间复杂度
在更新中getAnswer()，在最坏的情况下将不得不遍历整个树，即树的高度O(2*Log N)。2*log n因为这是最坏的情况，我们必须在左右子树中旅行，例如间隔[0-n-1]。
对于k查询，总体时间复杂度为O(K*log n).