struct node{ int data,lazy; }; void build(const vector&datas,vector&tree,int rt,int left,int right){ if(left == right){ tree[rt].data=datas[left]; return; } int mid = left+(right-left)/2; build(datas,tree,2*rt,left,mid); build(datas,tree,2*rt+1,mid+1,right); tree[rt].data = tree[2*rt].data+tree[2*rt+1].data; } void pushDown(vector&tree,int rt, int len){ if(tree[rt].lazy != 0){ tree[rt*2].data += tree[rt].lazy * (len - len/2); tree[rt*2].lazy += tree[rt].lazy; tree[rt*2+1].data += tree[rt].lazy * (len/2); tree[rt*2+1].lazy += tree[rt].lazy; tree[rt].lazy = 0; } } int query(vector&tree,int rt,int left,int right,int ql,int qr){ if(ql > right || qr < left){ return MIN; } if(ql <= left && qr >= right){ return tree[rt].data; } int mid = left+(right-left)/2; pushDown(tree,rt,right-left+1); int leftsum = query(tree,2*rt,left,mid,ql,qr); int rightsum = query(tree,2*rt+1,mid+1,right,ql,qr); return leftsum+rightsum; } void updata(vector&tree,int rt,int left,int right,int idx,int value){ if(left == right){ tree[rt].data = value; tree[rt].lazy = 0; return; } int mid = left+(right-left)/2; pushDown(tree,rt,right-left+1); if(idx<=mid){ updata(tree,2*rt,left,mid,idx,value); }else{ updata(tree,2*rt+1,mid+1,right,idx,value); } tree[rt].data = tree[2*rt].data+tree[2*rt+1].data; } void updataRange(vector&tree,int rt,int left,int right,int ul,int ur,int value){ if(ul>right||ur= right){ tree[rt].data += value * (right - left + 1); tree[rt].lazy += value; return; } int mid = left+(right-left)/2; pushDown(tree,rt,right-left+1); updataRange(tree,2*rt,left,mid,ul,ur,value); updataRange(tree,2*rt+1,mid+1,right,ul,ur,value); tree[rt].data=tree[2*rt].data+tree[2*rt+1].data; }