首页 > 代码库 > POJ 1195 2维线段树(树套树实现) 树状数组

POJ 1195 2维线段树(树套树实现) 树状数组

2024-07-04 18:54:08   225人阅读

   1:  #include <stdio.h>
   2:  #include <string.h>
   3:  #include <stdlib.h>
   4:  #include <algorithm>
   5:  #include <iostream>
   6:  using namespace std;
   7:   
   8:  #define LL(a)   a<<1
   9:  #define RR(a)   a<<1|1
  10:  const int MaxL = 1005;
  11:  struct sub_Seg_tree_node
  12:  {
  13:      int subleft,subright; // ydown = subleft, yup = subright
  14:  //    int maxval;  // the maval of the rect x [left,right], y [subleft, subright]
  15:      int sum;     // the sum of the num of point in rect x [left, right], y [subleft, subright]
  16:  };
  17:   
  18:  struct Seg_tree_node
  19:  {
  20:      int left,right;       // left = xleft, right = xright
  21:      sub_Seg_tree_node T[MaxL<<2];
  22:  } TT[MaxL<<2];
  23:   
  24:  void sub_build(int subl, int subr, int subidx, int idx)
  25:  {
  26:      TT[idx].T[subidx].subleft=subl;
  27:      TT[idx].T[subidx].subright=subr;
  28:  //    TT[idx].T[subidx].maxval=-1;
  29:      TT[idx].T[subidx].sum=0;
  30:      if(subl==subr)  return;
  31:      int mid=(subl+subr)>>1;
  32:      sub_build(subl, mid, LL(subidx), idx);
  33:      sub_build(mid+1, subr, RR(subidx), idx);
  34:  }
  35:   
  36:  void build(int l, int r, int subl, int subr, int idx)
  37:  {
  38:      TT[idx].left = l, TT[idx].right = r;
  39:      sub_build(subl, subr, 1, idx);
  40:      if(l==r) return;
  41:      int mid=(l+r)>>1;
  42:      build(l,mid,subl,subr, LL(idx));
  43:      build(mid+1,r,subl,subr, RR(idx));
  44:  }
  45:   
  46:  void sub_update(int y, int val, int subidx, int idx)
  47:  {
  48:      TT[idx].T[subidx].sum += val;
  49:  //    TT[idx].T[subidx].maxval=max(TT[idx].T[subidx].maxval, val);
  50:      if(TT[idx].T[subidx].subleft == TT[idx].T[subidx].subright) return;
  51:      int mid=(TT[idx].T[subidx].subleft+TT[idx].T[subidx].subright)>>1;
  52:      if(y <= mid)
  53:          sub_update(y, val, LL(subidx), idx);
  54:      else
  55:          sub_update(y, val, RR(subidx), idx);
  56:  }
  57:   
  58:  void update(int x, int y, int val, int idx)
  59:  {
  60:      sub_update(y, val, 1, idx);
  61:      if(TT[idx].left == TT[idx].right) return;
  62:      int mid=(TT[idx].left+TT[idx].right)>>1;
  63:      if( x<=mid)
  64:          update(x,y,val, LL(idx) );
  65:      else
  66:          update(x,y, val,RR(idx));
  67:  }
  68:   
  69:  //int sub_query(int subl, int subr, int subidx, int idx)
  70:  //{
  71:  //    if(TT[idx].T[subidx].subleft == subl && TT[idx].T[subidx].subright == subr)
  72:  //        return TT[idx].T[subidx].maxval;
  73:  //    int mid = (TT[idx].T[subidx].subleft + TT[idx].T[subidx].subright)>>1;
  74:  //    if(subr <= mid)
  75:  //        return sub_query(subl, subr, LL(subidx), idx);
  76:  //    else if(subl > mid)
  77:  //        return sub_query(subl, subr, RR(subidx), idx);
  78:  //    else
  79:  //        return max(sub_query(subl, mid, LL(subidx), idx),sub_query(mid+1, subr, RR(subidx), idx));
  80:  //}
  81:  //
  82:  //int query(int l, int r, int subl, int subr, int idx)
  83:  //{
  84:  //    if(TT[idx].left == l && TT[idx].right == r)
  85:  //        return sub_query(subl, subr, 1, idx);
  86:  //    int mid = (TT[idx].left + TT[idx].right)>>1;
  87:  //    if(r <= mid)
  88:  //        return query(l,r, subl,subr, LL(idx));
  89:  //    else if(l > mid)
  90:  //        return query(l, r, subl, subr, RR(idx));
  91:  //    else
  92:  //        return max(query(l, mid, subl, subr, LL(idx)),query(mid+1, r, subl,subr, RR(idx)));
  93:  //}
  94:   
  95:  int sub_query(int subl, int subr, int subidx, int idx)
  96:  {
  97:      if(TT[idx].T[subidx].subleft == subl && TT[idx].T[subidx].subright == subr)
  98:          return TT[idx].T[subidx].sum;
  99:      int mid = (TT[idx].T[subidx].subleft + TT[idx].T[subidx].subright)>>1;
 100:      if(subr <= mid)
 101:          return sub_query(subl, subr, LL(subidx), idx);
 102:      else if(subl > mid)
 103:          return sub_query(subl, subr, RR(subidx), idx);
 104:      else
 105:          return sub_query(subl, mid, LL(subidx), idx) + sub_query(mid+1, subr, RR(subidx), idx);
 106:  }
 107:   
 108:  int query(int l, int r, int subl, int subr, int idx)
 109:  {
 110:      if(TT[idx].left == l && TT[idx].right == r)
 111:          return sub_query(subl, subr, 1, idx);
 112:      int mid = (TT[idx].left + TT[idx].right)>>1;
 113:      if(r <= mid)
 114:          return query(l,r, subl,subr, LL(idx));
 115:      else if(l > mid)
 116:          return query(l, r, subl, subr, RR(idx));
 117:      else
 118:          return query(l, mid, subl, subr, LL(idx))+ query(mid+1, r, subl,subr, RR(idx));
 119:  }
 120:   
 121:  int x1[10005];
 122:  int y1[10005];
 123:  int x2[10005];
 124:  int y2[10005];
 125:  int px[10005];
 126:  int py[10005];
 127:  int pval[10005];
 128:  //
 129:  //int main()
 130:  //{
 131:  //    freopen("1.txt","r",stdin);
 132:  //    int NN,MM;
 133:  //    cin>>NN>>MM;
 134:  //
 135:  //    for(int i=0; i<NN; i++)
 136:  //        scanf("%d%d%d", &px[i],&py[i], &pval[i]);
 137:  //
 138:  //    for(int i=0; i<MM; i++)
 139:  //    {
 140:  //        scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
 141:  //        if(x1[i] > x2[i]) swap(x1[i], x2[i]);
 142:  //        if(y1[i] > y2[i]) swap(y1[i], y2[i]);
 143:  //    }
 144:  //
 145:  //    build(0, 1060, 0, 1060, 1);
 146:  //    for(int i=0; i<NN; i++)
 147:  //    {
 148:  //        cout<<"update point "<<px[i]<<" "<<py[i]<<endl;
 149:  //        update(px[i],py[i],pval[i], 1);
 150:  //    }
 151:  //
 152:  //    for(int i=0; i<MM; i++)
 153:  //    {
 154:  //        cout<<"query ret "<<x1[i]<<" "<<x2[i]<<" "<<y1[i]<<" "<<y2[i]<<endl;
 155:  //        cout<<"Ret "<<query(x1[i],x2[i],y1[i],y2[i],1)<<endl;
 156:  //    }
 157:  //
 158:  //    return 0;
 159:  //}
 160:  int s;
 161:  int main()
 162:  {
 163:  //    freopen("1.txt","r",stdin);
 164:      int i;
 165:      int sb;
 166:      int sb1,sb2,sb3,sb4;
 167:      scanf("%d",&sb);
 168:      while(sb!=3)
 169:      {
 170:          switch(sb)
 171:          {
 172:          case 0:
 173:              scanf("%d",&s);
 174:              build(0,s,0,s,1);
 175:              break;
 176:          case 1:
 177:              scanf("%d%d%d",&sb1,&sb2,&sb3);
 178:              update(sb1,sb2,sb3,1);
 179:              break;
 180:          case 2:
 181:              scanf("%d%d%d%d",&sb1,&sb2,&sb3,&sb4);
 182:              printf("%d\n",query(sb1,sb3,sb2,sb4,1));
 183:              break;
 184:          default:
 185:              goto ed;
 186:          }
 187:          scanf("%d",&sb);
 188:      }
 189:  ed:
 190:      ;
 191:      return 0;
 192:  }
<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>

 

树状数组来做这个题目相对来说简单得多!  树状数组则清楚得多.相对来说二维线段树用得比较少,而且功能都比较简单,查询平面矩形包含几个点,查询矩形最大值之类的.

 

   1:  #include <iostream>
   2:  #include <stdio.h>
   3:  #include <string.h>
   4:  using namespace std;
   5:   
   6:  #define MAX 1026
   7:  int s[MAX][MAX];
   8:  int lowbit(int x)
   9:  {
  10:      return x&(x^(x-1));
  11:  }
  12:   
  13:  int N;
  14:   
  15:  void change(int a,int b,int delta)
  16:  {
  17:      for(int x=a; x<=N; x+=lowbit(x))
  18:          for(int y=b; y<=N; y+=lowbit(y))
  19:              s[x][y]+=delta;
  20:  }
  21:  int sum(int a,int b)
  22:  {
  23:      int res=0;
  24:      for(int x=a; x>0; x-=lowbit(x))
  25:          for(int y=b; y>0; y-=lowbit(y))
  26:              res+=s[x][y];
  27:      return res;
  28:  }
  29:  int main()
  30:  {
  31:      int n;
  32:      while(cin>>n)
  33:      {
  34:          if(n==0)
  35:          {
  36:              cin>>N; N++;
  37:              memset(s,0,sizeof(s));
  38:          }
  39:          else if(n==1)
  40:          {
  41:              int a,b,c;
  42:              cin>>a>>b>>c; a++; b++;
  43:              change(a,b,c);
  44:          }
  45:          else if(n==2)
  46:          {
  47:              int a,b,c,d;
  48:              cin>>a>>b>>c>>d;
  49:              a++;b++;c++;d++;
  50:              cout<<sum(c,d) + sum(a-1,b-1) - sum(a-1,d) - sum(c,b-1)<<endl;
  51:          }
  52:          else break;;
  53:      }
  54:      return 0;
  55:  }
<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>


联系
我们