線分樹の学習:どのように線分樹で矩形面積を計算しますか?

30646 ワード
線分樹 矩形の面積 poj 1151 データ構造とアルゴリズム
線分樹は、離散的かつ線形的な思想にまたがる柔軟な区間管理機能を持つデータ構造です.
私たちが一番よく使う線分樹は区間求和です.
   
   
   
   
    
    
    
    
    
  1. /* 
    2. 
    
    
    
    
  2.  * InterverTree.cpp 
    3. 
    
    
    
    
  3.  * 
    4. 
    
    
    
    
  4.  *  Created on: 2012-11-1 
    5. 
    
    
    
    
  5.  *      Author: Administrator 
    6. 
    
    
    
    
  6.  */ 
    7. 
    
    
    
    
  7. #include 
    8. 
    
    
    
    
  8. #define M 100 
    9. 
    
    
    
    
  9. #define Mid(a,b) ((a)+(b))>>1 
    10. 
    
    
    
    
  10. int a[11]={0,1,2,3,4,5,6,7,8,9,10}; 
    11. 
    
    
    
    
  11. struct Tree{ 
    12. 
    
    
    
    
  12.     int left,right; 
    13. 
    
    
    
    
  13.     int key,sum; 
    14. 
    
    
    
    
  14. }tree[M]; 
    15. 
    
    
    
    
  15. /* 
    16. 
    
    
    
    
  16.  *    
    17. 
    
    
    
    
  17.  * */ 
    18. 
    
    
    
    
  18. void build(int id,int left,int right){ 
    19. 
    
    
    
    
  19.     tree[id].left=left; 
    20. 
    
    
    
    
  20.     tree[id].right=right; 
    21. 
    
    
    
    
  21.     if(left==right){ 
    22. 
    
    
    
    
  22.         tree[id].sum=tree[id].key=a[left]; 
    23. 
    
    
    
    
  23.         return; 
    24. 
    
    
    
    
  24.     } 
    25. 
    
    
    
    
  25.     int mid=Mid(left,right); 
    26. 
    
    
    
    
  26.     build(id*2,left,mid); 
    27. 
    
    
    
    
  27.     build(id*2+1,mid+1,right); 
    28. 
    
    
    
    
  28.     tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; 
    29. 
    
    
    
    
  29. } 
    30. 
    
    
    
    
  30. /* 
    31. 
    
    
    
    
  31.  *     
    32. 
    
    
    
    
  32.  * */ 
    33. 
    
    
    
    
  33. void update(int id,int pos,int key){ 
    34. 
    
    
    
    
  34.     if(tree[id].left==tree[id].right){ 
    35. 
    
    
    
    
  35.         tree[id].sum=tree[id].key=key; 
    36. 
    
    
    
    
  36.         return ; 
    37. 
    
    
    
    
  37.     } 
    38. 
    
    
    
    
  38.     int mid=Mid(tree[id].left,tree[id].right); 
    39. 
    
    
    
    
  39.  
    40. 
    
    
    
    
  40.     pos<=mid?update(id*2,pos,key):update(id*2+1,pos,key); 
    41. 
    
    
    
    
  41.  
    42. 
    
    
    
    
  42.     tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; 
    43. 
    
    
    
    
  43. } 
    44. 
    
    
    
    
  44. /* 
    45. 
    
    
    
    
  45.  *      
    46. 
    
    
    
    
  46.  * */ 
    47. 
    
    
    
    
  47. int query(int id,int left,int right){ 
    48. 
    
    
    
    
  48.     if(tree[id].left==left&&tree[id].right==right){ 
    49. 
    
    
    
    
  49.         return tree[id].sum; 
    50. 
    
    
    
    
  50.     } 
    51. 
    
    
    
    
  51.     int mid=Mid(tree[id].left,tree[id].right); 
    52. 
    
    
    
    
  52.  
    53. 
    
    
    
    
  53.     if(right<=mid){ 
    54. 
    
    
    
    
  54.         return query(id*2,left,right); 
    55. 
    
    
    
    
  55.     }else if(left>mid){ 
    56. 
    
    
    
    
  56.         return query(id*2+1,left,right); 
    57. 
    
    
    
    
  57.     }else{ 
    58. 
    
    
    
    
  58.         return query(id*2,left,mid)+query(id*2+1,mid+1,right); 
    59. 
    
    
    
    
  59.     } 
    60. 
    
    
    
    
  60. } 
    61. 
    
    
    
    
  61. int main(){ 
    62. 
    
    
    
    
  62.     build(1,1,10);//  a         ，0      
    63. 
    
    
    
    
  63.     int ans=query(1,1,5);//    [1,5]     
    64. 
    
    
    
    
  64.     printf("sum=%d
    "    ,ans); 
    65. 
    
    
    
    
  65.     update(1,5,0);//  5        
    66. 
    
    
    
    
  66.     ans=query(1,1,10); 
    67. 
    
    
    
    
  67.     printf("sum=%d
    "    ,ans); 
    68. 
    
    
    
    
  68.     return 0; 
    69. 
    
    
    
    
  69. } 
    70.
    上のように一番基礎的な線分樹です.典型的に空間で時間を変える方法です.また、線分ツリーは、ツリー型のデータ構造の慣行の特徴を継承しています.クエリの複雑さをO(n)からロゴ(n)に低減します.
    でも、普通は線分の木を使っています.こんなに真っ直ぐに使うことはできません.怠惰な操作は普通どこで使いますか?区間の更新など!区間を更新する時、私達は普通は直接馬鹿に行ってすべての点を更新するのではなくて、更新したい区間を先に記録して、それから区間のサブエリアを使う時、私達はやっと本当の更新に行きます.
   
   
   
   
    
    
    
    
    
  1. /* 
    2. 
    
    
    
    
  2.  * InterverTree.cpp 
    3. 
    
    
    
    
  3.  * 
    4. 
    
    
    
    
  4.  *  Created on: 2012-11-1 
    5. 
    
    
    
    
  5.  *      Author: Administrator 
    6. 
    
    
    
    
  6.  */ 
    7. 
    
    
    
    
  7. #include 
    8. 
    
    
    
    
  8. #define M 100 
    9. 
    
    
    
    
  9. #define Mid(a,b) ((a)+(b))>>1 
    10. 
    
    
    
    
  10. int a[11]={0,1,2,3,4,5,6,7,8,9,10}; 
    11. 
    
    
    
    
  11. struct Tree{ 
    12. 
    
    
    
    
  12.     int left,right; 
    13. 
    
    
    
    
  13.     int sum,add; 
    14. 
    
    
    
    
  14. }tree[M]; 
    15. 
    
    
    
    
  15. /* 
    16. 
    
    
    
    
  16.  *    
    17. 
    
    
    
    
  17.  * */ 
    18. 
    
    
    
    
  18. void build(int id,int left,int right){ 
    19. 
    
    
    
    
  19.     tree[id].left=left; 
    20. 
    
    
    
    
  20.     tree[id].right=right; 
    21. 
    
    
    
    
  21.     if(left==right){ 
    22. 
    
    
    
    
  22.         tree[id].sum=a[left]; 
    23. 
    
    
    
    
  23.         tree[id].add=0; 
    24. 
    
    
    
    
  24.         return; 
    25. 
    
    
    
    
  25.     } 
    26. 
    
    
    
    
  26.     int mid=Mid(left,right); 
    27. 
    
    
    
    
  27.     build(id*2,left,mid); 
    28. 
    
    
    
    
  28.     build(id*2+1,mid+1,right); 
    29. 
    
    
    
    
  29.     tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; 
    30. 
    
    
    
    
  30. } 
    31. 
    
    
    
    
  31.  
    32. 
    
    
    
    
  32. void push_down(int id){ 
    33. 
    
    
    
    
  33.     if(tree[id].add>0){ 
    34. 
    
    
    
    
  34.         tree[id].sum+=(tree[id].right-tree[id].left+1)*tree[id].add; 
    35. 
    
    
    
    
  35.         if(tree[id].left//      
    36. 
    
    
    
    
  36.             tree[id*2].add+=tree[id].add; 
    37. 
    
    
    
    
  37.             tree[id*2+1].add+=tree[id].add; 
    38. 
    
    
    
    
  38.         } 
    39. 
    
    
    
    
  39.         tree[id].add=0; 
    40. 
    
    
    
    
  40.     } 
    41. 
    
    
    
    
  41. } 
    42. 
    
    
    
    
  42. /* 
    43. 
    
    
    
    
  43.  *     
    44. 
    
    
    
    
  44.  * */ 
    45. 
    
    
    
    
  45. void update(int id,int pos,int key){ 
    46. 
    
    
    
    
  46.     push_down(id); 
    47. 
    
    
    
    
  47.     if(tree[id].left==tree[id].right){ 
    48. 
    
    
    
    
  48.         tree[id].sum=key; 
    49. 
    
    
    
    
  49.         return ; 
    50. 
    
    
    
    
  50.     } 
    51. 
    
    
    
    
  51.     int mid=Mid(tree[id].left,tree[id].right); 
    52. 
    
    
    
    
  52.  
    53. 
    
    
    
    
  53.     pos<=mid?update(id*2,pos,key):update(id*2+1,pos,key); 
    54. 
    
    
    
    
  54.  
    55. 
    
    
    
    
  55.     tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; 
    56. 
    
    
    
    
  56. } 
    57. 
    
    
    
    
  57. /* 
    58. 
    
    
    
    
  58.  *     ：   [left,right]    key 
    59. 
    
    
    
    
  59.  * */ 
    60. 
    
    
    
    
  60. void update_add(int id,int left,int right,int key){ 
    61. 
    
    
    
    
  61.     push_down(id); 
    62. 
    
    
    
    
  62.     if(tree[id].left==left&&tree[id].right==right){//        
    63. 
    
    
    
    
  63.         tree[id].add=key; 
    64. 
    
    
    
    
  64.         return; 
    65. 
    
    
    
    
  65.     } 
    66. 
    
    
    
    
  66.     int mid=Mid(tree[id].left,tree[id].right); 
    67. 
    
    
    
    
  67.     if(right<=mid){ 
    68. 
    
    
    
    
  68.         update_add(id*2,left,right,key); 
    69. 
    
    
    
    
  69.     }else if(left>mid){ 
    70. 
    
    
    
    
  70.         update_add(id*2+1,left,right,key); 
    71. 
    
    
    
    
  71.     }else{ 
    72. 
    
    
    
    
  72.         update_add(id*2,left,mid,key); 
    73. 
    
    
    
    
  73.         update_add(id*2+1,mid+1,right,key); 
    74. 
    
    
    
    
  74.     } 
    75. 
    
    
    
    
  75. } 
    76. 
    
    
    
    
  76. /* 
    77. 
    
    
    
    
  77.  *      
    78. 
    
    
    
    
  78.  * */ 
    79. 
    
    
    
    
  79. int query(int id,int left,int right){ 
    80. 
    
    
    
    
  80.     push_down(id); 
    81. 
    
    
    
    
  81.     if(tree[id].left==left&&tree[id].right==right){ 
    82. 
    
    
    
    
  82.         return tree[id].sum; 
    83. 
    
    
    
    
  83.     } 
    84. 
    
    
    
    
  84.     int mid=Mid(tree[id].left,tree[id].right); 
    85. 
    
    
    
    
  85.     if(right<=mid){ 
    86. 
    
    
    
    
  86.         return query(id*2,left,right); 
    87. 
    
    
    
    
  87.     }else if(left>mid){ 
    88. 
    
    
    
    
  88.         return query(id*2+1,left,right); 
    89. 
    
    
    
    
  89.     }else{ 
    90. 
    
    
    
    
  90.         return query(id*2,left,mid)+query(id*2+1,mid+1,right); 
    91. 
    
    
    
    
  91.     } 
    92. 
    
    
    
    
  92. } 
    93. 
    
    
    
    
  93. int main(){ 
    94. 
    
    
    
    
  94.     build(1,1,10);//  a         ，0      
    95. 
    
    
    
    
  95.     int ans=query(1,1,5);//    [1,5]     
    96. 
    
    
    
    
  96.     printf("sum=%d
    "    ,ans); 
    97. 
    
    
    
    
  97.     update(1,6,10); 
    98. 
    
    
    
    
  98.     //    
    99. 
    
    
    
    
  99.     update_add(1,1,5,10); 
    100. 
    
    
    
    
  100.     ans=query(1,1,6); 
    101. 
    
    
    
    
  101.     printf("ans=%d
    "    ,ans); 
    102. 
    
    
    
    
  102.     return 0; 
    103. 
    
    
    
    
  103. } 
    104.
    これも線分樹の基礎操作であり、一般的には初歩的な線分樹は誤った領域に入りやすいです.つまり線分樹は配列だけを操作することができます.線分樹建樹も必ずbuild(id*2、left、mid)、build(id*2＋1、mid+1、right)です.このように線分樹を理解すると、大間違いです.
   線分樹はデータ構造ですが、データ構造は私達の生活の中で現実的なものが極めて抽象的な結晶です.私たちがやるべきことは、物事を分析し、現象を通して本質を見ることです.この点は話しやすいですが、やってみると難しいです.
難しいですが、やはりやります.それは線分樹の幾何学的応用である.もっと直接に話してください.
どのように線分を線分の木で表しますか?例えば線分[1,5]は線分樹でどう表しますか?それとも前の木のように:[1,1][2,2]、[3,3]、[4,5]ですか?それはだめです
私たちはこのように木を建てました.[1,2][2,3][3,4][4,5]の中には元の線分の概念が含まれています.
    また、線分の長さが大きい場合や、線分が浮動小数点型のデータであれば、線分を離散化する必要があります.離散化の方法も簡単です.例えば、三本の線分があります.1.1-2.2  3.3-1.5 8.8-100.1私たちは長さ6の配列で保存できます.そして、下のマーカーにkeyを加えてツリーを作ります.これで線分が一つ離散化します.
    考えが分析されたら、一つの問題で悟りを深めることができます.線分樹の水問題poj 1151
ブログを参照してください:http://blog.csdn.net/tsaid/article/details/6706893
  
   
   
   
   
    
    
    
    
    
  1. #include 
    2. 
    
    
    
    
  2. #include 
    3. 
    
    
    
    
  3. using namespace std; 
    4. 
    
    
    
    
  4. #define M 1000 
    5. 
    
    
    
    
  5. #define eps 1e-8 
    6. 
    
    
    
    
  6. struct Tree{ 
    7. 
    
    
    
    
  7.     int ll,rr,cover;//   cover    int   bool             
    8. 
    
    
    
    
  8.     double lf,rf; 
    9. 
    
    
    
    
  9.     double len; 
    10. 
    
    
    
    
  10. }tree[4*M]; 
    11. 
    
    
    
    
  11. struct Line{ 
    12. 
    
    
    
    
  12.     double x,y1,y2; 
    13. 
    
    
    
    
  13.     int flag; 
    14. 
    
    
    
    
  14. }line[M]; 
    15. 
    
    
    
    
  15. double y[M];//     y    
    16. 
    
    
    
    
  16. int cmp_double(const double &d1,const double &d2){ 
    17. 
    
    
    
    
  17.     double d=d1-d2; 
    18. 
    
    
    
    
  18.     if(d>eps)//d1>d2 
    19. 
    
    
    
    
  19.         return 1; 
    20. 
    
    
    
    
  20.     else if(d//d1 
    21. 
    
    
    
    
  21.         return -1; 
    22. 
    
    
    
    
  22.     else //d1==d2 
    23. 
    
    
    
    
  23.         return 0; 
    24. 
    
    
    
    
  24. } 
    25. 
    
    
    
    
  25. //     
    26. 
    
    
    
    
  26. bool cmp(const Line &l1,const Line &l2){//        
    27. 
    
    
    
    
  27.         return l1.x
    28. 
    
    
    
    
  28. } 
    29. 
    
    
    
    
  29. //   
    30. 
    
    
    
    
  30. void build(int id,int ll,int rr){ 
    31. 
    
    
    
    
  31.     tree[id].ll=ll;tree[id].rr=rr; 
    32. 
    
    
    
    
  32.     tree[id].lf=y[ll],tree[id].rf=y[rr]; 
    33. 
    
    
    
    
  33.     tree[id].len=tree[id].cover=0; 
    34. 
    
    
    
    
  34.     if(ll+1==rr)return;//        ，       
    35. 
    
    
    
    
  35.     int mid=(ll+rr)>>1; 
    36. 
    
    
    
    
  36.     build(id*2,ll,mid); 
    37. 
    
    
    
    
  37.     build(id*2+1,mid,rr); 
    38. 
    
    
    
    
  38. } 
    39. 
    
    
    
    
  39. void lenght(int id){//             
    40. 
    
    
    
    
  40.     if(tree[id].cover>0){ 
    41. 
    
    
    
    
  41.         tree[id].len=tree[id].rf-tree[id].lf; 
    42. 
    
    
    
    
  42.     }else if(tree[id].ll+1==tree[id].rr){//    
    43. 
    
    
    
    
  43.         tree[id].len=0; 
    44. 
    
    
    
    
  44.     }else 
    45. 
    
    
    
    
  45.         tree[id].len=tree[id*2].len+tree[id*2+1].len; 
    46. 
    
    
    
    
  46. } 
    47. 
    
    
    
    
  47. //    
    48. 
    
    
    
    
  48. void update(int id,Line line){ 
    49. 
    
    
    
    
  49.     if(cmp_double(tree[id].lf,line.y1)==0&&cmp_double(tree[id].rf,line.y2)==0){ 
    50. 
    
    
    
    
  50.         tree[id].cover+=line.flag; 
    51. 
    
    
    
    
  51.         lenght(id); 
    52. 
    
    
    
    
  52.         return; 
    53. 
    
    
    
    
  53.         //         ，      ， 
    54. 
    
    
    
    
  54.         //          ，       mid    
    55. 
    
    
    
    
  55.  
    56. 
    
    
    
    
  56.     }else if(cmp_double(line.y1,tree[2*id+1].lf)>=0){//            
    57. 
    
    
    
    
  57.         update(id*2+1,line); 
    58. 
    
    
    
    
  58.     }else if(cmp_double(line.y2,tree[id*2].rf)<=0){//            
    59. 
    
    
    
    
  59.         update(id*2,line); 
    60. 
    
    
    
    
  60.     }else{//       
    61. 
    
    
    
    
  61.         Line tmp; 
    62. 
    
    
    
    
  62.         tmp=line;tmp.y2=tree[id*2].rf; 
    63. 
    
    
    
    
  63.         update(2*id,tmp); 
    64. 
    
    
    
    
  64.         tmp=line;tmp.y1=tree[id*2+1].lf; 
    65. 
    
    
    
    
  65.         update(2*id+1,tmp); 
    66. 
    
    
    
    
  66.     } 
    67. 
    
    
    
    
  67.     lenght(id);//        ，     len     
    68. 
    
    
    
    
  68. } 
    69. 
    
    
    
    
  69. int main(){ 
    70. 
    
    
    
    
  70.     int n; 
    71. 
    
    
    
    
  71.     int i,t,ti=0; 
    72. 
    
    
    
    
  72.     while(scanf("%d",&n)&&n){ 
    73. 
    
    
    
    
  73.         double x1,y1,x2,y2; 
    74. 
    
    
    
    
  74.         for(t=i=1;i<=n;i++){ 
    75. 
    
    
    
    
  75.             scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); 
    76. 
    
    
    
    
  76.             line[t].x=x1; 
    77. 
    
    
    
    
  77.             line[t].y1=y1; 
    78. 
    
    
    
    
  78.             line[t].y2=y2; 
    79. 
    
    
    
    
  79.             line[t].flag=1; 
    80. 
    
    
    
    
  80.             y[t]=y1; 
    81. 
    
    
    
    
  81.             t++; 
    82. 
    
    
    
    
  82.             line[t].x=x2; 
    83. 
    
    
    
    
  83.             line[t].y1=y1; 
    84. 
    
    
    
    
  84.             line[t].y2=y2; 
    85. 
    
    
    
    
  85.             line[t].flag=-1; 
    86. 
    
    
    
    
  86.             y[t]=y2; 
    87. 
    
    
    
    
  87.             t++; 
    88. 
    
    
    
    
  88.         } 
    89. 
    
    
    
    
  89.         sort(line+1,line+t,cmp); 
    90. 
    
    
    
    
  90.         sort(y+1,y+t);//       
    91. 
    
    
    
    
  91.  
    92. 
    
    
    
    
  92.         build(1,1,t-1); 
    93. 
    
    
    
    
  93.         update ( 1, line[1] );//          
    94. 
    
    
    
    
  94.         double ans=0.00; 
    95. 
    
    
    
    
  95.         for(i=2;i
    96. 
    
    
    
    
  96.             ans+=tree[1].len*(line[i].x-line[i-1].x); 
    97. 
    
    
    
    
  97.             update(1,line[i]);//          ，     
    98. 
    
    
    
    
  98.         } 
    99. 
    
    
    
    
  99.         printf("Test case #%d
    "    ,++ti); 
    100. 
    
    
    
    
  100.         printf("Total explored area: %.2lf

    "    ,ans); 
    101. 
    
    
    
    
  101.  
    102. 
    
    
    
    
  102.     } 
    103. 
    
    
    
    
  103.     return 0; 
    104. 
    
    
    
    
  104. } 
    105.
       また、矩形分割も矩形領域に関する問題を解くことができます.
1.eosio.token.hpp