1 #include<cstdio> 2 #include<algorithm> 3 #include<math.h> 4 using namespace std; 5 const int Nmax=100005; 6 int num,block,l[Nmax],r[Nmax],n,q,belong[Nmax]; 7 long long Max[Nmax],a[Nmax]; 8  9 void build()10 {11     block=sqrt(n);12     num=n/block; 13     if(n%block) num++;14     for(int i=1;i<=n;i++)15     {16         l[i]=(i-1)*block+1;17         r[i]=i*block;18         belong[i]=(i-1)/block+1;19     }20     r[num]=n;21     22     for(int i=1;i<=n;i++)23         a[i]=0;24 25     for(int i=1;i<=num;i++)26         for(int j=l[i];j<=r[i];j++)27             Max[j]=max(Max[j],a[j]);28 }29 30 void update(int x,int data)31 {32     a[x]+=data;33     Max[belong[x]]=max(Max[belong[x]],a[x]);34 }35 36 long long ask(int x,int y)37 {38     long long ans=0;39     if(belong[x]==belong[y])40     {41         for(int i=x;i<=y;i++)42         {43             ans=max(ans,a[i]);44         }45         return ans;46     }47     for(int i=x;i<=r[x];i++)48         ans=max(ans,a[i]);49     for(int i=belong[x]+1;i<belong[y];i++)50         ans=max(ans,Max[i]);51     for(int i=l[y];i<=y;i++)52         ans=max(ans,a[i]);53     return ans;54 }55 56 int main()57 {58     scanf("%d%d",&n,&q);59     while(q--)60     {61         int c,x,y;62         scanf("%d%d%d",&c,&x,&y);63         if(c==1)64             update(x,y);65         else66             printf("%lld\n",ask(x,y));67     }68     return 0;69 }