线段树复习

线段树复习

class RangeTree {
 int curV;
 int curL;
 int curR;
 int curM;
 RangeTree left;
 RangeTree right;

 RangeTree(int length) {
  this(0, length - 1);
 }

 RangeTree(int l, int r) {
  curL = l;
  curR = r;
  curM = curL + (curR - curL) / 2;
  if (curL != r) {
   left = new RangeTree(curL, curM);
   right = new RangeTree(curM + 1, curR);
  }
 }

 void insert(int i, int num) {
  curV += num;
  if (curL != curR) {
   if (i <= curM) {
    left.insert(i, num);
   } else {
    right.insert(i, num);
   }
  }
 }

 int search(int tarL, int tarR) {
  if (curL == tarR) {
   return curV;
  } else {
   if (tarR <= curM) {
    return left.search(tarL, tarR);
   } else if (curM < tarL) {
    return right.search(tarL, tarR);
   } else {
    return left.search(tarL, curM) + right.search(curM + 1, tarR);
   }
  }
 }
}