基本上就是个简单的线段树的单点修改（update）与区间查询（query）连Lazy标记都不用

传送门：

 

若是初学线段树 hdu1754也是道不错的题

传送门：

题解的传送门：

附上代码（T1166）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int maxn=50000+10; 7 int n,m,i,j,T,a[maxn],sumt[maxn*4]; 8 char s[20]; 9 int max(int a,int b) {
   return a>b?a:b;}10 int min(int a,int b) {
   return a
         
          0?a:-a;}12 int gcd(int a,int b) {
   return b==0?a:gcd(b,a%b);}13 void build(int node,int s,int t)14 {15      if (s==t){sumt[node]=a[s]; return;}16      int mid=(s+t)/2,lson=2*node,rson=lson+1;17      build(lson,s,mid);18      build(rson,mid+1,t);19      sumt[node]=sumt[lson]+sumt[rson];20 }21 void update(int node,int s,int t,int id,int add)22 {23      if (s==t){sumt[node]+=add; return;}24      int mid=(s+t)/2,lson=2*node,rson=lson+1;25      if (id<=mid) update(lson,s,mid,id,add);26              else update(rson,mid+1,t,id,add);27      sumt[node]=sumt[lson]+sumt[rson];28 }29 int query(int node,int s,int t,int L,int R)30 {31     if (t
          
         
        
       
      
     

 

 

顺便，这里有一个线段树模板（无Lazy标记的）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6  7 const int maxn=50000+10; 8 int n,m,i,j,a[maxn]; 9 int max(int a,int b) {
   return a>b?a:b;}10 int min(int a,int b) {
   return a
         
          %d\n",s,t);16      int mid=(s+t)/2,lson=2*node,rson=lson+1;17      printf("min=%d max=%d\n",mint[node],maxt[node]);18      printf("sum=%d\n",sumt[node]);19      if (s==t) return;20      outp(lson,s,mid);21      outp(rson,mid+1,t);22      mint[node]=min(mint[lson],mint[rson]);23      maxt[node]=max(maxt[lson],maxt[rson]);24      sumt[node]=sumt[lson]+sumt[rson];25 }26 void build(int node,int s,int t)27 {28      if (s==t)29      {30          sumt[node]=a[s];31          mint[node]=a[s];32          maxt[node]=a[s];33          return;34      }35      int mid=(s+t)/2,lson=2*node,rson=lson+1;36      build(lson,s,mid);37      build(rson,mid+1,t);38      mint[node]=min(mint[lson],mint[rson]);39      maxt[node]=max(maxt[lson],maxt[rson]);40      sumt[node]=sumt[lson]+sumt[rson];41 }42 void update(int node,int s,int t,int id,int add)43 {44      if (s==t)45      {46          sumt[node]+=add;47          mint[node]+=add;48          maxt[node]+=add;49          return;50      }51      int mid=(s+t)/2,lson=2*node,rson=lson+1;52      if (id<=mid) update(lson,s,mid,id,add);53              else update(rson,mid+1,t,id,add);54      mint[node]=min(mint[lson],mint[rson]);55      maxt[node]=max(maxt[lson],maxt[rson]);56      sumt[node]=sumt[lson]+sumt[rson];57 }58 int query(int node,int s,int t,int L,int R)59 {60     if (t
          
         
        
       
      
     

 

比较简陋，只支持区间求和，区间最大最小值

 

还望大神不吝赐教，斧正斧正