谁家橙题这么难，建议升绿）））

看见“区间和”这三个字，你想到了什么？

当然是 前缀和 线段树啊。

再来看数据，高达 $10^4$，说明暴力肯定做不了了，我们只能老老实实的打线段树了。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace fast{
    #define int long long
    #ifdef __linux__
    #define gc getchar_unlocked
    #define pc putchar_unlocked
    #else
    #define gc _getchar_nolock
    #define pc _putchar_nolock
    #endif
    inline bool blank(const char x) {return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
    template<typename Tp> inline void read(Tp &x) {x=0; register bool z=true; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=(x<<1)+(x<<3)+(a^48); x=(z?x:~x+1);}
    inline void read(double &x) {x=0.0; register bool z=true; register double y=0.1; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=x*10+(a^48); if(a!='.') return x=z?x:-x,void(); for(a=gc();isdigit(a);a=gc(),y/=10) x+=y*(a^48); x=(z?x:-x);}
    inline void read(char &x) {for(x=gc();blank(x)&&(x^-1);x=gc());}
    inline void read(char *x) {register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) *x++=a; *x=0;}
    inline void read(string &x) {x=""; register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) x+=a;}
    template<typename T,typename ...Tp> inline void read(T &x,Tp &...y) {read(x),read(y...);}
    template<typename Tp> inline void write(Tp x) {if(!x) return pc(48),void(); if(x<0) pc('-'),x=~x+1; register int len=0; register char tmp[64]; for(;x;x/=10) tmp[++len]=x%10+48; while(len) pc(tmp[len--]);}
    inline void write(const double x) {register int a=6; register double b=x,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); pc('.'); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);}
    inline void write(const pair<int,double>x) {register int a=x.first; if(a<7) {register double b=x.second,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); a&&(pc('.')); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);} else cout<<fixed<<setprecision(a)<<x.second;}
    inline void write(const char x) {pc(x);}
    inline void write(const bool x) {pc(x?49:48);}
    inline void write(char *x) {fputs(x,stdout);}
    inline void write(const char *x) {fputs(x,stdout);}
    inline void write(const string &x) {fputs(x.c_str(),stdout);}
    template<typename T,typename ...Tp> inline void write(T x,Tp ...y) {write(x),write(y...);} 
}using namespace fast;
const int N=4000005;
vector<int> a(N);
class segment_tree{
    private:
        struct node{
            int lazy=0,data;
        }tree[N];
        int left_child(int now){//取左孩子，返回的是索引
            return 2*now;
        }int right_child(int now){//取右孩子
            return 2*now+1;
        }void pushdown(int now,int l,int r){//懒标记的处理
            if(tree[now].lazy!=0){
                int mid=(l+r)/2;
                tree[left_child(now)].data+=tree[now].lazy*(mid-l+1);
                tree[left_child(now)].lazy+=tree[now].lazy;
                tree[right_child(now)].data+=tree[now].lazy*(r-mid);
                tree[right_child(now)].lazy+=tree[now].lazy;
                tree[now].lazy=0;
            }
        }
    public:
        void build(int now,int l,int r){//递归建树
            tree[now].lazy=0;//懒标记的初始化，后面会讲
            if(l==r){//叶子节点
                tree[now].data=a[l];
                return ;
            }int mid=l+(r-l)/2;
            build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
            tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;//赋值该节点为他的左右孩子节点值之和。
        }
        long long query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
            if(ql>r or qr<l)return 0;
            if(ql<=l and qr>=r)return tree[now].data;
            int mid=l+(r-l)/2;
            pushdown(now,l,r);
            return query_add(left_child(now),l,mid,ql,qr)+query_add(right_child(now),mid+1,r,ql,qr);
        }
        void update(int now,int l,int r,int idx,int val){//单点更新
            if(l==r){
                tree[now].data=val;
                return ;
            }int mid=l+(r-l)/2;
            pushdown(now,l,r); 
            if(idx<=mid){
                update(left_child(now),l,mid,idx,val);
            }else{
                update(right_child(now),mid+1,r,idx,val);
            }tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
        }
        void update_range(int now,int l,int r,int ul,int ur,int val){//区间更新
            if(ul>r or ur<l)return ;
            if(ul<=l and ur>=r){
                tree[now].data+=1LL*val*(r-l+1);
                tree[now].lazy+=val;
                return ;
            }int mid=l+(r-l)/2;
            pushdown(now,l,r);
            update_range(left_child(now),l,mid,ul,ur,val);
            update_range(right_child(now),mid+1,r,ul,ur,val);
            tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
        }
};
signed main(){
    segment_tree tree;
    int n,m;
    read(n,m);
    for(int i=1;i<=n;i++)cin >> a[i];
    tree.build(1,1,n);
    while(m--){
        int l,r;
        cin >> l >> r;
        write(tree.query_add(1,1,n,l,r),'\n');
    }
    return 0;
}  

时间复杂度 $\mathcal{O}(n+m\log n)$。

线段树板子，建议升绿（

（效率还不如前缀和