Index Tree概念

Index Tree 是一个满二叉树。修改与查询复杂度为O(logN)
大数据量级别的数据，重复被计算使用时，优先考虑index Tree 的数据结构。

Index Tree 的特点

    • 有且只有一个根节点
    • 每个父节点都有一个左子节点和右子节点
    • Index Tree每一层节点个数满足2^n
    • 左子节点满足偶数特性，右边满足奇数特性
    • 父节点=子节点/2
    • 节点总数为 2n-1 ，n为最底层叶子节点的数量


Index Tree 的构造

Index Tree可使用一维数组进行存储，通过确定最后一层节点个数来确定树的大小。
题目一般给定N的个数： int [] Tree = new int Tree[2*cnt]
最后一层节点的个数同时也是，最后一层第一个节点 Tree[] 数组下标。

  1. int cnt = 1;
  2. while(cnt < N){
  3.     cnt<<=1;   //通过N 来确定最底层叶子节点的个数
  4. }
  5. Tree = new int[2*cnt];  // 2*cont 开辟满树的大小数组
  6. for(int i=0;i<2*cnt;i++){
  7.     Tree[i]=0;            //Tree 数组的初始化
  8. }

Index Tree解题思路

  • 第一步 定义tree的存储类型，数组或list
  • 第二步 读入数据 计算出节点数量
  • 第三步 通过节点数量计算出 满二叉树的最底层节点的个数 n
  • 第四步 通过满二叉树的最底层节点数量 创建满二叉树的一维数组 2n-1 的大小，同时也确定了最底层节点第一个节点的一维数组的下标也为n
  • 第五步 排序
  • 第六步 实现算法（查找树，更新树）query 方法查询 记录数据， upde 方法更新树的结构 一遍下次使用
  • 输出

    练习题目：

    描述：
    草原上有一群牛，每个牛都有自己的吃草区域[S，E]，
    假如两头牛的区域分别为[Si，Ei]，[Sj,Ej]; 如果Si<=Sj,并且Ej <= Ei, 那么i牛就比j牛厉害
    现在题目中给出N个牛，请计算比自己厉害的牛的个数
    输入
    N 牛的个数 （1<=N<=100000）
    下面N行给出区域
    N (1 <= N <= 105),
    E(0 <= S < E <= 105)， S 和 E(0 <= S < E <= 100000)
    输入结束行是 0.
    输出
    输入比自己厉害的个数
    输入
    4
    1 2
    0 3
    3 4
    2 5
    0
    答案：
    1 0 1 0

    分析

    1.排序：
    如果S相等，E按降序排列
    如果S不相等，按照S升序排列
    ——>因为已按开始点进行排序，早出现区域的开始点肯定是小于等于当前区域的开始点，因此只需要判断结束点就ok了。
    此题目需要注意，存在相同的区域，相同区域的两个牛之间不进行比较

代码

  1. package indexTree;
  2. import java.io.BufferedReader;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5. import java.util.Comparator;
  6. import java.util.StringTokenizer;
  8. /**
  9.  * 
  10.  * @author XA-GDD
  11.  */
  12. public class cow {
  13.         static int N;
  14.         static int sumtree[] = new int[100001*4];
  15.         static class info{
  16.             int idx, s, e;
  17.             info(int idx, int s, int e){
  18.                 this.idx = idx;  //数据原始的  id  坐标
  19.                 this.s = s;        //开始时间
  20.                 this.e = e;        //结束时间
  21.             }
  22.         }
  23.         static info D[] = new info[100001];      //对象数组
  24.         static int ans[] = new int[100001];   //结果数组
  25.         static class comp implements Comparator<info>{
  26.             @Override
  27.             public int compare(info a, info b) {
  28.                 if(a.s != b.s) return a.s-b.s;
  29.                 else return b.e-a.e;
  30.             }
  31.         }
  32.         //更新树的节点
  33.         static void update(int node){
  34.             int cur=node;
  35.             while(cur>0){
  36.                 sumtree[cur]++;
  37.                 cur>>=1;
  38.             }
  39.         }
  40.                         //   11-10       15
  41.         //树的查询
  42.         static int query(int start, int end){
  43.             int ret=0;
  44.             int s=start;
  45.             int e=end;
  46.             while(s<=e){
  47.                 if(s%2==1) ret += sumtree[s];
  48.                 if(e%2==0) ret += sumtree[e];
  49.                 s = (s+1)>>1;
  50.                 e = (e-1)>>1;
  51.             }
  52.             return ret;
  53.         }
  55.         public static void main(String[] args) throws Exception{
  56.             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  57.             StringTokenizer st;
  58.             while(true){
  59.                 N = Integer.parseInt(br.readLine());
  60.                 if(N==0) break;
  61.                 int Nidx = 1;
  62.                 //100000 代表的是   S,E的最大值
  63.                 while(Nidx<100000) {
  64.                     Nidx<<=1;   //计算出最下层节点需要的叶子节点的个数 
  65.                                 //同时也是最下一层叶子节点的第一个Tree 的下标
  66.                 }            // 2*n 代表的是  tree 的最打节点个数       2*n-1
  68. //                Arrays.fill(sumtree, 0);    //fill 的实际处理也是通过for 循环填充的了整个数组的值，  每次的循环次数为  100001*4 效率相对低
  69.                 for(int i=0;i<Nidx*2;i++) {
  70.                     sumtree[i]=0;   // 初始化数组的值    将数组的值清空   
  71.                 }
  73. //                Arrays.fill(ans, 0);        //for 循环填充的了整个数组的值  每次的循环次数为  100001
  74.                 for(int i=0,s,e;i<N;i++){
  75.                     st = new StringTokenizer(br.readLine());
  76.                     s = Integer.parseInt(st.nextToken());
  77.                     e = Integer.parseInt(st.nextToken());
  78.                     D[i] = new info(i,s,e);
  79.                     ans[i]=0;   //结果的数组   初始化
  80.                 }
  81.                 Arrays.sort(D,0,N,new comp());
  82.                 for(int i=0,scnt=0;i<N;i++){
  83.                     if(i>0 && D[i-1].s == D[i].s && D[i-1].e == D[i].e) {
  84.                         scnt++;
  85.                     }else {
  86.                         scnt = 0;
  87.                     }                    
  88.                     //  11 - 10       15
  89.                     ans[D[i].idx] = query(Nidx+D[i].e,Nidx+100000)-scnt;
  90.                     update(Nidx+D[i].e);
  91.                 }
  92.                 for(int i=0;i<N;i++) {
  93.                     System.out.print(ans[i]+" ");
  94.                 }
  95.                 System.out.println();
  96.             }
  97.         }
  98. }