原题解

本题在原题解的基础上，消除了一些瑕疵，有以下瑕疵：

这是线段树模板 \(P3372\) 【模板】线段树\(1\) 的第一篇题解，和\(ppt\)中代码稍有区别的地方在于：
在\(query\)的代码里，如果查询区间和结点区间不相交的时候没有直接返回，感觉这个代码里仍然向下递归，会一直递归到叶子结点。当然这时候的递归呈现一条链状结构，或者一直向左下，或者一直向右下。一直到最下面的叶子结点。
所以最好在\(query\)里加一行代码：
\(if(q_x>r || l>q_y)\) \(return 0;\)
但是事实上不会这样
因为下面的判断中：
\(if(q_x<=mid)\) \(res+=query(q_x,q_y,l,mid,ls(p));\)
\(if(q_y>mid)\) \(res+=query(q_x,q_y,mid+1,r,rs(p));\)
保证了如果出现\(q_x>r\) \(||\) \(l>q_y\);
其实直接就\(return\) \(res\)了，而此时\(res\)的值就是\(0\).

修改过后的题解

#include<iostream>
#include<cstdio>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x) {
    return x<<1;//左儿子
}
inline ll rs(ll x) {
    return x<<1|1;//右儿子 
}
inline void push_up(ll p) {//每个结点表示一个区间，记录本区间的和 
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r) {
    if(l==r) {
        ans[p]=a[l];
        return ;
    }//如果左右区间相同，那么必然是叶子节点啦，只有叶子节点是被真实赋值的
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    //此处由于我们采用的是二叉树，所以对于整个结构来说，可以用二分来降低复杂度，否则树形结构则没有什么明显的优化
    push_up(p);
    //此处由于我们是要通过子节点来维护父亲节点，所以pushup的位置应当是在回溯时。
}
inline void f(ll p,ll l,ll r,ll k) {
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k*(r-l+1);
    //由于是这个区间统一改变，所以ans数组要加元素个数次啦 
}
//我们可以认识到，f函数的唯一目的，就是记录当前节点所代表的区间 
inline void push_down(ll p,ll l,ll r) {
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
    //每次更新两个儿子节点。以此不断向下传递 
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k) {
    //nl,nr为要修改的区间
    //l,r,p为当前节点所存储的区间以及节点的编号 
    if(nl<=l&&r<=nr) {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    //回溯之前（也可以说是下一次递归之前，因为没有递归就没有回溯） 
    //由于是在回溯之前不断向下传递，所以自然每个节点都可以更新到 
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
    //回溯之后 
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p) {
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid) res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}
int main() {
    ll op,l,r,k;
    cin>>n>>m;//n个数 m次询问 
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    build(1,1,n);//建树 
    while(m--) {
        scanf("%lld",&op);//操作方式 
        switch(op) {
            case 1: {
                scanf("%lld%lld%lld",&l,&r,&k);
                update(l,r,1,n,1,k);
                break;
            }
            case 2: {
                scanf("%lld%lld",&l,&r);
                printf("%lld\n",query(l,r,1,n,1));
                break;
            }
        }
    }
    return 0;
}