• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Reiks的技術博客

            C/C++/STL/Algorithm/D3D
            posts - 17, comments - 2, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            線段樹

            Posted on 2009-08-28 09:11 reiks 閱讀(299) 評論(0)  編輯 收藏 引用 所屬分類: 算法與數據結構
            #include <iostream>   
            using namespace std;   
            #define N 100   
            struct TNode   
            {   
                
            int left, right;   
                
            int n;   
            }
            ;   
            TNode T[N
            *2+1];   
            void build(int s, int t, int step)   
            {   
                T[step].left 
            = s;   
                T[step].right 
            = t;   
                T[step].n 
            = 0;   
                
            if(s == t)   
                    
            return;   
                
            int mid = (s + t) / 2;   
                build(s, mid, step
            *2);   
                build(mid
            +1, t, step*2+1);   
            }
               
            void insert(int s, int t, int step)   
            // insert [s, t] in the tree   
            {   
                
            if(s == T[step].left && t == T[step].right)   
                
            {   
                    T[step].n
            ++;   
                    
            return;   
                }
               
                
            int mid = (T[step].left + T[step].right) / 2;   
                
            if(t <= mid)   
                    insert(s, t, step
            *2);   
                
            else if(s > mid)   
                    insert(s, t, step
            *2+1);   
                
            else  
                
            {   
                    insert(s,mid, step
            *2);   
                    insert(mid
            +1, t, step*2+1);   
                }
               
            }
               
            void calculate(int s, int t, int step, int target, int& count)   
            // caculate target in the tree   
            {   
                count 
            += T[step].n;   
                
            if(s == t)   
                    
            return;   
                
            int mid = (s + t) / 2;   
                
            if(target <= mid)   
                    calculate(s, mid, step
            *2, target, count);   
                
            else  
                    calculate(mid
            +1, t, step*2+1, target, count);   
            }
               
            int main()   
            {   
                build(
            071);   
                insert(
            251);   
                insert(
            461);   
                insert(
            071);   
                
            int count = 0;   
                calculate(
            0714, count);   
                cout  
            << count << endl;   
                
            return 0;   
            }
              
            伊人久久五月天| 秋霞久久国产精品电影院| 久久国产精品免费一区| 亚洲国产精品一区二区三区久久| 久久99九九国产免费看小说| 99久久精品费精品国产一区二区| 国产精品伊人久久伊人电影| 亚洲?V乱码久久精品蜜桃 | 精品国产青草久久久久福利| 无夜精品久久久久久| 久久99中文字幕久久| 免费精品国产日韩热久久| 亚洲一本综合久久| 久久精品国产99国产精品亚洲| 亚洲国产精品久久| 亚洲乱码精品久久久久..| 国产成人综合久久精品尤物| 久久久国产乱子伦精品作者| 亚洲一级Av无码毛片久久精品| 香蕉久久夜色精品国产小说| 久久综合给合久久狠狠狠97色69| 亚洲精品成人久久久| 久久最近最新中文字幕大全| 日本强好片久久久久久AAA| 日本欧美国产精品第一页久久| 久久精品国产亚洲AV麻豆网站| 三级三级久久三级久久| 污污内射久久一区二区欧美日韩 | 久久这里只有精品18| 思思久久99热只有频精品66| 国产精品嫩草影院久久| 老司机国内精品久久久久| 九九久久99综合一区二区| 国产精品一区二区久久国产| 新狼窝色AV性久久久久久| 色综合久久久久久久久五月| 国内精品伊人久久久久777| 亚洲人成无码网站久久99热国产 | 色偷偷88欧美精品久久久| 久久国产视屏| 日本高清无卡码一区二区久久|