线段树

推荐：http://blog.csdn.net/x314542916/article/details/7837276
  1 //建树 
  2  struct SgtNode {
  3     int sum, l, r, ch[2];
  4 } sgt[maxn];
  5 int sgtBuild(int l, int r) {
  6     int p = tot ++;
  7     sgt[p].l = l, sgt[p].r = r;
  8     sgt[p].sum = 0;
  9     if (l + 1 < r) {
 10         int mid = (l + r) >> 1;
 11         sgt[p].ch[0] = sgtBuild(l, mid);
 12         sgt[p].ch[1] = sgtBuild(mid, r);
 13     }
 14     return p;
 15 }
 16 //单点修改 
 17 void sgtChange(int p, int pos, int delta) {
 18     sgt[p].sum += delta;
 19     if (sgt[p].l + 1 < sgt[p].r) {
 20         int mid = (sgt[p].l + sgt[p].r)>> 1;
 21         if (pos < mid) {
 22             sgtChange(sgt[p].ch[0], pos, delta);
 23         } else {
 24             sgtChange(sgt[p].ch[1], pos, delta);
 25         }
 26     }
 27 //区间求和 
 28 int sgtSum(int p, int l, int r) {
 29     if (sgt[p].l == l && sgt[p].r == r) {
 30         return sgt[p].sum;
 31     } else {
 32         int mid = (sgt[p].l + sgt[p].r)>> 1;
 33         if (r <= mid) {
 34             return sgtSum(sgt[p].ch[0], l, r);
 35         } else if (l >= mid) {
 36             return sgtSum(sgt[p].ch[1], l, r);
 37         } else {
 38             return sgtSum(sgt[p].ch[0], l, mid) + sgtSum(sgt[p].ch[1], mid, r);
 39         }
 40     }
 41 }
 42 //给一个区间加某数字 
 43 void sgtRangeAdd(int p, int l, int r, int delta) {
 44     sgt[p].sum += delta * (r - l);
 45     if (sgt[p].l == l && sgt[p].r == r) {
 46         sgt[p].addtag += delta;
 47     } else {
 48         int mid = (sgt[p].l + sgt[p].r)>> 1;
 49         if (r <= mid) {
 50             sgtRangeAdd(sgt[p].ch[0], l, r, delta);
 51         } else if (l >= mid) {
 52             sgtRangeAdd(sgt[p].ch[1], l, r, delta);
 53         } else {
 54             sgtRangeAdd(sgt[p].ch[0], l, mid, delta);
 55             sgtRangeAdd(sgt[p].ch[1], mid, r, delta);
 56         }
 57     }
 58 }
 59 //把一段区间改为某一个数字 
 60 void update(int p) {
 61     if (sgt[p].settag != -1) {
 62         sgt[p].sum = sgt[p].settag * (sgt[p].r - sgt[p].l);
 63     } else if (sgt[p].l + 1 < sgt[p].r) {
 64         sgt[p].sum = sgt[sgt[p].ch[0]].sum + sgt[sgt[p].ch[1]].sum;
 65     }
 66 }
 67 void pushDown(int p) {
 68     if (sgt[p].settag != -1) {
 69         sgt[sgt[p].ch[0]].settag = sgt[p].settag;
 70         update(sgt[p].ch[0]);
 71         sgt[sgt[p].ch[1]].settag = sgt[p].settag;
 72         update(sgt[p].ch[1]);
 73         sgt[p].settag = -1;
 74     }
 75 }
 76 void sgtRangeSet(int p, int l, int r, int value) {
 77     if (sgt[p].l == l && sgt[p].r == r) {
 78         sgt[p].settag = value;
 79         update(sgt[p]);
 80     } else {
 81         pushDown(p);
 82         int mid = (sgt[p].l + sgt[p].r)>> 1;
 83         if (r <= mid) {
 84             sgtRangeSet(sgt[p].ch[0], l, r, value);
 85         } else if (l >= mid) {
 86             sgtRangeSet(sgt[p].ch[1], l, r, value);
 87         } else {
 88             sgtRangeSet(sgt[p].ch[0], l, mid, value);
 89             sgtRangeSet(sgt[p].ch[1], mid, r, value);
 90         }
 91         update(p);
 92     }
 93 }
 94 int sgtSum(int p, int l, int r) {
 95     if (sgt[p].l == l && sgt[p].r == r) {
 96         return sgt[p].sum;
 97     } else {
 98         int mid = (sgt[p].l + sgt[p].r)>> 1;
 99         int influ = (r - l) * sgt[p].addtag;
100         if (r <= mid) {
101             return sgtSum(sgt[p].ch[0], l, r) + influ;
102         } else if (l >= mid) {
103             return sgtSum(sgt[p].ch[1], l, r) + influ;
104         } else {
105             return sgtSum(sgt[p].ch[0], l, mid) + sgtSum(sgt[p].ch[1], mid, r) + influ;
106         }
107     }
108 }