学步园

//线段树  用来存取1-n 这条线段中 
整数点出现的次数，已经一段中所有点出现的次数
//扩展 可以把整数点映射成n个实体， 
每个实体会存放着一点资源，  线段树在大规模读取连续数的时候存在着优势
public class LineTree {
    int[]
tree;
    int
size;

    public
LineTree(int n) {
  
   
 tree = new int[n * 4 + 1]; // 抛弃掉0点 方便index的扩张
e.g 1的子节点为2， 3 2的子节点为3 4
  
   
 size = n;
    }
    
    public
static void main(String[] args){
  
   
 //test case  
acm_116
  
   
 LineTree lineTree  = new
LineTree(5);
  
   
 lineTree.Update(1, 1);
  
   
 lineTree.Update(2, 2);
  
   
 lineTree.Update(3, 3);
  
   
 lineTree.Update(4, 4);
  
   
 lineTree.Update(5, 5);
       
System.out.println(lineTree.Query(1, 3));
       
lineTree.Update(1, 2);
       
System.out.println(lineTree.Query(1, 3));
       
lineTree.Update(2, 3);
       
System.out.println(lineTree.Query(1, 2));
       
System.out.println(lineTree.Query(1, 5));
    }

    public void
init() throws Exception {
  
   
 if (tree == null) {
  
   
   
 throw new Exception("tree 未初始化");
  
   
 }
  
   
 for (int i = 0; i < tree.length; i++) {
  
   
   
 tree[i] = 0;
  
   
 }
  
   
 size = 0;
    }

    //
在这条线段中的n节点 插入权值value；
    public void
Update(int n, int value) {
  
   
 Update(1, 1, size, n, value);
    }

    private void
Update(int index, int left, int right, int n, int value) {
  
   
 tree[index] += value;
  
   
 if (left == right) {
  
   
   
 return;
  
   
 } else {
  
   
   
 int mid = (left + right) >> 1;
  
   
   
 if (mid >= n) {