Interval tree, or Segment tree is a basic data structure in computer science, which is also useful in ICPC.

Introduction

Pass, please refer to Wikipedia

Style of code

• rt: root
• maxn: The max interval that the problem requests
• lson and rson: left son and right son

Build by recursion

• push_up: update the sum to the parent node
• build : build the interval tree at first

void push_up(int rt) {
  sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void build(int l, int r, int rt){
  if (l==r) {
    scanf("%d",&sum[rt]);
    return;
  }
  int m=(l+r)>>1;
  build(lson);
  build(rson);
  push_up(rt);
}

Query by recursion

• query: return the sum value of the interval

int query(int L, int R, int l, int r, int rt){
  if (L<=l && r<=R){
    return sum[rt];
  }
  int m=(l+r)>>1;
  int ret=0;
  if (L<=m) ret += query(L, R, lson);
  if (R>m) ret += query(L, R ,rson);
  return ret;
}

Update one node

• update: update one node’s value

void update(int p,int add,int l, int r, int rt) {
  if (l==r) {
    sum[rt]+=add;
    return ;
  }
  int m=(l+r)>>1;
  if (p<=m) update(p, add, lson);
  else update(p, add, rson);
  push_up(rt);
}

HDU 1166 is a naked problem that we need to update one node’s value and query the interval’s sum:

HDU 1754 is also a easy problem that we need to update one node:

HDU 1394 is a classic problem but I can not do it yet.

Update interval

Lazy Propagation(Lazy update operation)

When you update the interval of the data, you will not need to modify all of the node in this interval. Instead, you can mark the node to indicate that all of the child of it have an increasement on it.

• push_down: push the lazy mark down to the left child and right child
• update: update an interval’s value

void push_down(int rt,int m) {
  if(col[rt]) {
    col[rt<<1] = col[rt<<1|1] = col[rt];
    sum[rt<<1] = (m - (m>>1)) * col[rt];
    sum[rt<<1|1] = (m>>1) * col[rt];
    col[rt]= 0;
  }
}

void update(int p,int add,int l, int r, int rt) {
  if (l==r) {
    sum[rt]+=add;
    return ;
  }
  int m=(l+r)>>1;
  if (p<=m) update(p, add, lson);
  else update(p, add, rson);
  push_up(rt);
}

HDU 1698 is a naked problem that we need to update one interval’s information:

Reference:

Slides by Guowei - PKU

Introduction to interval tree by NotOnlySuccess

A good article by letuskode

Wikipedia