初学线段树（SegmentTree）

从HH大神那你学来的模板风格。

感觉确实相当飘逸。

现在做了4题。。单点更新的，

想放上来，，以后慢慢整理！！

·单点更新」　　　　　　·刷题参考」

• hdu1166 敌兵布阵
  • 线段树第一题，单点更新第一题，可以作为线段树的模板，
  • 思路：兵工厂作为数量n映射作为线段总长，更具输入进行单点的更新与查询，sub操作可以理解为add一个负数　
  • Query操作：区间求和 update操作：单点的增减
  • 

     1 #include<cstdio>
     2 
     3 #define lson l, m, rt<<1
     4 #define rson m + 1, r, rt<<1 | 1
     5 #define mid(a,b) (a+b)>>1
     6 #define maxn 55555
     7 
     8 int sum[maxn<<2];
     9 
    10 void PushUP(int rt)
    11 {
    12     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    13 }
    14 
    15 void Build(int l,int r,int rt)
    16 {
    17     if(l == r)
    18     {
    19         scanf("%d",&sum[rt]);
    20         return;
    21     }
    22     int m = mid(l,r);
    23     Build(lson);
    24     Build(rson);
    25     PushUP(rt);
    26 }
    27 
    28 void Update(int p,int add,int l,int r,int rt)
    29 {
    30     if(l == r)
    31     {
    32         sum[rt] += add;
    33         return;
    34     }
    35     int m = mid(l,r);
    36     if(p <= m)
    37         Update(p,add,lson);
    38     else
    39         Update(p,add,rson);
    40     
    41     PushUP(rt);
    42 }
    43 
    44 int Query(int L,int R,int l,int r,int rt)
    45 {
    46     if(L <= l && r<= R)
    47     {
    48         return sum[rt];
    49     }
    50     int m = mid(l,r);
    51     int ans = 0;
    52     if(L <= m)
    53         ans += Query(L,R,lson);
    54     if(R > m)
    55         ans += Query(L,R,rson);
    56         
    57     return ans;
    58 }
    59 
    60 
    61 int main()
    62 {
    63     int T,n,a,b;
    64     scanf("%d",&T);
    65     for(int cas=1;cas<=T;cas++)
    66     {
    67         printf("Case %d:\n",cas);
    68         scanf("%d",&n);
    69         Build(1,n,1);
    70         
    71         char op[10];
    72         
    73         while(scanf("%s",op) && op[0] != ‘E‘)
    74         {
    75             scanf("%d %d",&a,&b);
    76             if(op[0] == ‘Q‘)
    77                 printf("%d\n",Query(a,b,1,n,1));
    78             else if(op[0] == ‘S‘)
    79                 Update(a,-b,1,n,1);
    80             else
    81                 Update(a,b,1,n,1);
    82         }    
    83     }
    84     return 0;
    85 }

    View Code
• hdu1754 I Hate It
  • Query操作：区间最值 update操作：单点替换
  • 

     1 #include<cstdio>
     2 #include<algorithm>
     3 using namespace std;
     4 #define lson l, m, rt<<1
     5 #define rson m + 1, r, rt<<1 | 1
     6 #define mid(l,r) (l+r)>>1
     7 #define maxn 222222
     8 
     9 int MAX[maxn<<2];
    10 
    11 void PushUP(int rt)
    12 {
    13     MAX[rt] = max(MAX[rt<<1],MAX[rt<<1|1]);
    14 }
    15 
    16 void Build(int l,int r,int rt)
    17 {
    18     if(l == r)
    19     {
    20         scanf("%d",&MAX[rt]);
    21         return;
    22     }
    23     int m = mid(l,r);
    24     Build(lson);
    25     Build(rson);
    26     PushUP(rt);
    27 }
    28 
    29 void Update(int p,int sc,int l,int r,int rt)
    30 {
    31     if(l == r)
    32     {
    33         MAX[rt] = sc;
    34         return;
    35     }
    36     int m = mid(l,r);
    37     if(p <= m)
    38         Update(p,sc,lson);
    39     else
    40         Update(p,sc,rson);
    41     PushUP(rt);
    42 }
    43 
    44 int Query(int L,int R,int l,int r,int rt)
    45 {
    46     if(L <= l && r <= R)
    47         return MAX[rt];
    48     int m = mid(l,r);
    49     int ans = 0;
    50     if(L <= m)
    51         ans = max(ans,Query(L,R,lson));
    52     if(R > m)    
    53         ans = max(ans,Query(L,R,rson));
    54     
    55     return ans;
    56 }
    57 
    58 
    59 
    60 int main()
    61 {
    62     int n,m,a,b;
    63     while(~scanf("%d%d",&n,&m))
    64     {
    65         Build(1,n,1);    
    66         while(m--)
    67         {
    68             char op[2];
    69             scanf("%s%d%d",op,&a,&b);
    70             if(op[0] == ‘Q‘)
    71                 printf("%d\n",Query(a,b,1,n,1));
    72             else
    73                 Update(a,b,1,n,1);    
    74         }
    75     }
    76     return 0;
    77 } 

    View Code
• hdu1394 Minimum Inversion Number 
• 这里学习到了逆序数的求法，归并排序求，线段树，树状数组，点树
  • 求逆序数的方法     
  • 1394方法总结
  • 思路：每插入一个数，就进行一次询问并更新(询问当前线段树中比X小的数的个数，询问区间为[x,n-1])
  •   注：因为插入的数不会有重复且为0到N-1，所以询问时应该是在区间[x,n-1]
  • 　关于逆序数递推：求出原序列的逆序数后，通过递推确定最小的逆序数 
  •   这里把一个数x移到末尾，比x小的数[0...x-1]共x个都在x的前面了 ，逆序数减少x
  •        比x大的树[x+1...N-1]共n-1-x个都在x的前面了，逆序数增加n-1-x个
  • 　     最后的逆序数变化为  res = res + n-1-x - x = res + n-1-2*x
  • Query操作：区间求和 update操作：单调增减
  • 

     1 #include<cstdio>
     2 #include<cstring>
     3 #include<algorithm>
     4 using namespace std;
     5 #define maxn 5555
     6 #define CLR(a,b) memset(a,b,sizeof(a))
     7 #define lson l, m, rt << 1
     8 #define mid(l,r) (l+r)>>1
     9 #define rson m+1, r, rt << 1 | 1
    10 
    11 
    12 int sum[maxn<<2];
    13 int x[maxn],n;
    14 
    15 void PushUP(int rt)
    16 {
    17     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    18 }
    19 
    20 
    21 void Update(int p,int l,int r,int rt)
    22 {
    23     if(l == r)
    24     {
    25         sum[rt]++;
    26         return;
    27     }
    28     int m = mid(l,r);
    29     if(p <= m)
    30         Update(p,lson);
    31     else
    32         Update(p,rson);
    33     PushUP(rt);    
    34 }
    35 
    36 int Query(int L,int R,int l,int r,int rt)
    37 {
    38     if(L <= l && r <= R)
    39         return sum[rt];
    40     int m = mid(l,r);
    41     int ans = 0;
    42     if(L <= m)
    43         ans += Query(L,R,lson);
    44     if(R > m)
    45         ans += Query(L,R,rson);
    46     return ans;
    47 }
    48 
    49 
    50 int main()
    51 {
    52     while(~scanf("%d",&n))
    53     {
    54         CLR(sum,0);
    55         int res = 0;
    56         for(int i=0;i<n;i++)
    57         {
    58             scanf("%d",&x[i]);
    59             res += Query(x[i],n-1,0,n-1,1);
    60             Update(x[i],0,n-1,1);
    61         }
    62         int ret = res;
    63         for(int i=0;i<n;i++)
    64         {
    65             res += n - 1 - x[i] - x[i];
    66             ret = min(ret,res);
    67         }
    68         printf("%d\n",ret);
    69     }
    70 
    71     return 0;
    72 }

    View Code
• hdu2795 Billboard
  • 思路： 将h这一维映射到线段树的区间，w这一维对应区间点上的最大值，
  •   每次询问的时候（询问先左后右），做一次插入的操作，相应的h维度的值减少wi
  •   参考blog
  • Query操作： 返回区间最大值的位置（hh大神直接把update写里面了）
  • 

     1 #include<cstdio>
     2 #include<algorithm>
     3 using namespace std;
     4 
     5 #define lson l, m, rt << 1
     6 #define rson m+1, r, rt << 1 | 1
     7 #define mid(l,r) (l+r) >> 1
     8 #define maxn 222222
     9 
    10 int MAX[maxn<<2];
    11 int h,w,n;
    12 
    13 void PushUP(int rt)
    14 {
    15     MAX[rt] = max(MAX[rt<<1], MAX[rt<<1|1]);
    16 }
    17 
    18 void Build(int l,int r,int rt)
    19 {
    20     MAX[rt] = w;
    21     if(l == r)
    22         return;
    23     int m = mid(l,r);
    24     Build(lson);
    25     Build(rson);
    26 }
    27 
    28 int Query(int x,int l,int r,int rt)
    29 {
    30     if(l == r)        //找到可以放置的位置 
    31     {
    32         MAX[rt] -= x;
    33         return l;
    34     }
    35     int m = mid(l,r);
    36     int ret = (MAX[rt<<1] >= x) ? Query(x,lson) : Query(x,rson);
    37     PushUP(rt);
    38     return ret;    
    39 }
    40 
    41 int main()
    42 {
    43     while(~scanf("%d%d%d",&h,&w,&n))
    44     {
    45         h = min(h,n);
    46         Build(1,h,1);
    47         while(n--)
    48         {
    49             int x;
    50             scanf("%d",&x);
    51             if(MAX[1] < x)    puts("-1");
    52             else    printf("%d\n",Query(x,1,h,1));
    53         }
    54     }
    55     return 0;
    56 }

    View Code