题解 | 【模板】动态区间和Ⅱ ‖ 区间修改 + 区间查询

#include <iostream>
#include <memory>
#include <vector>
using namespace std;
using ll=long long;
//定义二叉树
struct TreeNode{
    int l,r;
    ll sum=0;
    ll lazy_tag=0;
    unique_ptr<TreeNode> left;
    unique_ptr<TreeNode> right;
    TreeNode(int l,int r,ll sum):l(l),r(r),sum(sum),left(nullptr),right(nullptr){}
};
//定义全局sum数组
vector<ll> sum;
//定义arr数组
vector<int> arr;
//构建求和数组
void buildSumArr(int n){
    sum[1]=arr[1];
    for(int i=2;i<=n;i++){
        sum[i]=sum[i-1]+arr[i];
    }
}
//构建线段树
void buildSegmentTree(unique_ptr<TreeNode>& node){
    if(node->l==node->r) return;
    int mid=(node->l+node->r)/2;
    ll leftSum=sum[mid]-sum[node->l-1];
    ll rightSum=sum[node->r]-sum[mid];
    node->left=make_unique<TreeNode>(node->l,mid,leftSum);
    buildSegmentTree(node->left);
    node->right=make_unique<TreeNode>(mid+1,node->r,rightSum);
    buildSegmentTree(node->right);
}
//下推
void upDown(unique_ptr<TreeNode>& node){
    if(node->left==nullptr || node->right==nullptr) return;
    if(node->lazy_tag!=0){
        node->left->sum+=node->lazy_tag*(node->left->r-node->left->l+1);
        node->right->sum+=node->lazy_tag*(node->right->r-node->right->l+1);
        node->left->lazy_tag+=node->lazy_tag;
        node->right->lazy_tag+=node->lazy_tag;
        node->lazy_tag=0;
    }
}
//实现节点更新
void update(int L,int R,int x,unique_ptr<TreeNode>& node){
    if(node->l>=L && node->r<=R){
        node->sum+=(ll)x*(node->r-node->l+1);
        node->lazy_tag+=x;
    }else{
        upDown(node);
        //假设目标区间为【1，8】，mid为4，左子树为【1，4】，
        //右子树为【5，8】
        //查询【2，6】，则
        // 递归更新左右子树
        if (node->left&& L <= node->left->r ) {
            update(L, R, x, node->left);
        }
        if (node->right && R>=node->right->l) {
            update(L, R, x, node->right);
        }
         // 更新当前节点
        if (node->left && node->right) {
            node->sum = node->left->sum + node->right->sum;
        }
    }
}
//实现查询操作
void query(int L,int R,ll& totalSum,unique_ptr<TreeNode>& node){
    if(node->l>=L && node->r<=R){
        totalSum+=node->sum;
    }else{
        upDown(node);
        if (node->left&& L <= node->left->r ) {
            query(L, R, totalSum, node->left);
        }
        if (node->right && R>=node->right->l) {
            query(L, R, totalSum, node->right);
        }
    }
}
int main(){
    int n,q;
    cin>>n>>q;
    arr.resize(n+1, 0);
    sum.resize(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    buildSumArr(n);
    unique_ptr<TreeNode> root=make_unique<TreeNode>(1,n,sum[n]);
    buildSegmentTree(root);
    while(q--){
        int op;
        cin>>op;
        int l,r;
        cin>>l>>r;
        if(op==1){
            int x;
            cin>>x;
            update(l, r, x, root);
        }else{
            ll totalSum=0;
            query(l, r, totalSum, root);
            cout<<totalSum<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")