线段树 一 基本操作

    (参考https://blog.csdn.net/zearot/article/details/48299459以及Clove_unique的csdn博客)
    线段树解决的是具有区间加法性质的统计，可以对连续的点进行修改，进行查询，做到单次复杂度为log的情况。
    主要操作为建树,单点修改，区间修改，区间查询，从上到下维护lazy标记，从下往上维护区间信息这5个基本操作。
    下面以维护区间和为例
1.存储结构

a[N]                       原数组   
lx[N<<2]                线段树上维护的信息
lazy[N<<2]            延迟标记

2.从下往上维护区间信息
    这种操作是底部的点被更改，然后递归返回，维护上面节点所使用的。

void push_up(int now)
{
  lx[now]=lx[now<<1]+lx[now<<1|1];
}

3.从上往下维护lazy标记
    lazy标记是区间修改的关键，lazy标记的存在导致只有在区间修改或者区间查询的递归过程中需要使用时，才进行操作，使用push_down将下一层的情况处理完，然后lazy标记传给下一层。

void push_down(int now,int le,int re)//now 线段树节点 le,re线段树左右子串大小
{
    if(lazy[now])
    {
        lazy[now<<1]+=lazy[now];
        lazy[now<<1|1]+=lazy[now];
        lx[now<<1]+=le*lazy[now];
        lx[now<<1|1]+=re*lazy[now];
        lazy[now]=0;
    }
}

4.建树
递归建树

void build(int l,int r,int now)
{
    if(l==r)
    {
        lx[now]=a[l];
        return;
    }
    int mid=(l+r)>>1; 
    build(l,mid,now<<1);
    build(mid+1,r,now<<1|1);
    push_up(now);
}

5.单点修改

void upd(int l,int r,int now,int id,int var)  //l,r是now节点的区间
{
    if(l==r)
    {
        lx[now]=var;
        return;
    }   
    int mid=(l+r)>>1;
    if(id<=mid)
     upd(l,mid,now<<1,id,var);
    else
     upd(mid+1,r,now<<1|1,id,var);
    push_up(now);
}

6.区间修改以及区间查询
区间修改和区间查询代码比较类似，都是自上而下进行处理

void upd_s(int l,int r,int now,int idx,int idy,int var) //[idx,idy]修改的区间
{
      if(l>=idx&&r<=idy)
    {
        lx[now]+=var*(r-l+1);
        lazy[now]=var;
        return ;
    }//now节点范围在修改区间内，维护now节点的信息
   //和now节点范围有交集，需要进入now的左右子树，所以先要push_down
    int mid=(l+r)>>1;
    push_down(now,mid-l+1,r-mid);
 //检测和左右子树是否有交集
    if(idx<=mid) upd_s(l,mid,now<<1,idx,idy,var);
    if(idy>mid)  upd_s(mid+1,r,now<<1|1,idx,idy,var);
//维护now节点
    push_up(now);
}
int  cal(int l,int r,int now,int idx,int idy) //[idx,idy]查询的区间
{
    if(l>=idx&&r<=idy)
    {
        return lx[now];
    }   //now节点范围在查询区间内
    int mid=(l+r)>>1;
    push_down(now,mid-l+1,r-mid);
    int ans=0;
    if(idx<=mid) ans+=(ans,cal(l,mid,now<<1,idx,idy));
    if(idy>mid)  ans+=(ans,cal(mid+1,r,now<<1|1,idx,idy));
    return ans;
}

补充
java的版 leetcode307 参照http://www.cnblogs.com/yrbbest/p/5056739.html

class NumArray {
    private class SegmentTreeNode {
        public int start;
        public int end;
        public int sum;
        public SegmentTreeNode left, right;
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            this.sum = 0;
        }
    }
    
    private SegmentTreeNode root;
    
    public NumArray(int[] nums) {
        this.root = buildTree(nums, 0, nums.length - 1);    
    }

    public void update(int i, int val) {
        update(root, i, val);
    }
     private void update(SegmentTreeNode node, int position, int val) {
        if(node.start == position && node.end == position) {
            node.sum = val;
            return;
        }
        int mid = node.start + (node.end - node.start) / 2;
        if(position <= mid) {
            update(node.left, position, val);
        } else {
            update(node.right, position, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }
    public int sumRange(int i, int j) {
       return sumRange(root, i, j);
        
    }
    
    private int sumRange(SegmentTreeNode node, int lo, int hi) {
        if(node.start >= lo && node.end <= hi) {
            return node.sum;
        }
        int mid = node.start + (node.end - node.start) / 2;
        int ans=0;
        if(lo <= mid) {
             ans+=sumRange(node.left, lo, hi);
        } 
        if (hi > mid)
        {
             ans+=sumRange(node.right, lo, hi);
        }
        return ans;
        
    }
     private SegmentTreeNode buildTree(int[] nums, int lo, int hi) {
        if(lo > hi) {
            return null;
        } else {
            SegmentTreeNode node = new SegmentTreeNode(lo, hi);
            if(lo == hi) {
                node.sum = nums[lo];
            } else {
                int mid = lo + (hi - lo) / 2;
                node.left = buildTree(nums, lo, mid);
                node.right = buildTree(nums, mid + 1, hi);
                node.sum = node.left.sum + node.right.sum;
            }
            return node;
        }
    }
}