세그먼트트리

세그먼트 트리 공식

void build(int id = 1, int l=0, int r=n){     if(r-l<2){         s[id]=a[l];         return;     }     int mid = (l+r)/2;     build(id*2, l, mid);     build(id*2+1, mid, r);     //first set the children and set its order     s[id]= s[id*2] + s[id*2+1];  } void modify(int p, int x, int id=1, int l=0, int r=n){     s[id]+=x-a[p];     if(r-l < 2){        a[p]=x;        return;     }     int mid=(l+r)/x;     if(p<mid)         modify(p, x, id*2, l, mid);     else         modify(p, x, id*2+1, mid, r);  } //x, y is range where you want to find sum int sum(int x, int y, int id=1, int l=0, int r=n){      if(x>=r || l>=y) return 0;      if(x<=l && r<=y) return s[id];      int mid=(l+r)/2;            return sum(x, y, id*2, l, mid)+      sum(x, y, id*2+1, mid, r); }