Segment tree

segment tree维护某个范围内的某个值，这个值要能随着两个范围的合并快速合并。segtree要支持范围修改，即快速对范围内的每个值做某个操作，或者查询范围内的值，一个segtree包含一个tree数组，一个update数组，用来标记是否有懒更新（有时候change数组里val为0不一定是没有懒更新），一个change数组记录懒更新的值

基本模板，如果range长度为n，则tree arr长度为4(n+1)比较好，idx是对应范围[left, right]的idx，由于segtree是存在一个完全二叉树array里的，最大的范围idx是1，左半边idx是2*idx，右半边idx是2*idx+1；

query(jobl, jobr, left, right)的含义是查询left和right在jobl和jobr范围内被覆盖到部分的值

query :
 if  [jobl, jobr] 包含 [left, right]:
    return tree[idx]
 if jobl <= mid:
     query in [left, mid]   
 if jobr >  mid:
     query in [mid+1, right]
 res = sum of both sub range   

懒更新，对一个范围修改时不去修改segtree里子范围里的值，而是只对当前范围做修改，然后把修改值缓存在change数组里有必要时再下发

update:
 if  [jobl, jobr] 包含 [left, right]:
    //当前范围被要求范围覆盖时懒住，没有必要再往下发，因为我们暂时不关心子范围的值
    //但是仍然会update当前层
    lazyupdate(idx)
    return
    
 //非全覆盖时，需要分别update左右被覆盖的部分   
 down() //将已有的懒更新值下发一层  
 if jobl <= mid:
     update in [left, mid]   
 if jobr >  mid:
     update in [mid+1, right]
 //左右update之后需要汇总回上一层，上一层还没有被update到    
 up()        

up:
   this is just summing up tree[idx*2] and tree[idx*2+1] to tree[idx]

lazyupdate会update当前idx的val，并记录需要下发的val信息。它被用在两个地方，第一是直接的update指令发到了某个被覆盖的范围上，第二是当前层有懒信息需要下发时会把消息懒到下一层去

lazyupdate:    
    update[idx]=true
    change[idx]=val
    tree[idx]=val

down是懒信息的下发，并会清空当前层的懒信息

down:
    if update[idx]:
        lazyupdate(idx*2+1)
        lazyupdate(idx*2)
        update[idx]=false;