zkw线段树

        class SegmentTree{
        int n;
        int[] st;
            public SegmentTree(int[] nums) {
                n = nums.length;
                st = new int[2*n];
                for(int i = n; i < 2*n; i++) st[i] = nums[i-n];
                for(int i = n-1; i > 0; i--) st[i] = st[2*i] + st[2*i+1];
            }

            public void update(int i, int val) {
                int diff = val - st[i+n];
                for(i+=n; i > 0; i/=2) st[i] += diff;
            }

            public int sumRange(int i, int j) {
                int res = 0;
                for(i+=n,j+=n; i <= j; i/=2,j/=2) {
                    if(i % 2 == 1) res += st[i++];//st[i]是右子节点
                    if(j % 2 == 0) res += st[j--];//st[j]是左子节点
                }
                return res;
            }
        };

int st[maxn];
int n;

void SegmentTree(int* nums) {
    for(int i = n; i < 2*n; i++) st[i] = nums[i-n];
    for(int i = n-1; i > 0; i--) st[i] = st[2*i] + st[2*i+1];
}


void update(int i, int diff) {
    //int diff = val - st[i+n];
    for(i+=n; i > 0; i/=2) st[i] += diff;
}

int sumRange(int i, int j) {
    int res = 0;
    for(i+=n,j+=n; i <= j; i/=2,j/=2) {
        if(i % 2 == 1) res += st[i++];
        if(j % 2 == 0) res += st[j--];
    }
    return res;
}

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int T[maxn<<2],m,n;

void build() {
    for(m=1; m<=n+1; m<<=1);
    for(int i=1; i<=n; ++i) T[i+m]=read();
    for(int i=m-1; i; --i)  T[i]=T[i<<1]+T[i<<1|1];
}

void updata(int x,int val) {
    T[x+=m]+=val;
    for(x>>=1; x>=1; x>>=1) T[x]=T[x<<1]+T[x<<1|1];
}

int query(int l,int r) {
    int ans=0;
    for(l=l+m-1,r=r+m+1; l^r^1; l>>=1,r>>=1) {
        if(~l&1)ans+=T[l^1];
        if(r&1) ans+=T[r^1];
    }
    return ans;
}