线段树

建立

private int[] d;
public void build(int s, int t, int p){
    if (s == t){
        d[p] = a[s];
        return ;
    }
    m = s + ((t-s) >> 1);
    build(s,m,p*2);
    build(m+1,t,p*2+1);
    d[p] = d[p*2] + d[(p*2) + 1];
}

查询

public int getSum(int l, int r, int s, int t. int p) {
    if (l <= s && r >= t){
        return d[p];
    }
    int m = s + ((t-s) >> 1), sum = 0;
    if (l <= m) sum += getSum(l, r, s, m, p*2);
    if (r > m) sum += getSum(l,r,m+1,t,p*2+1);
    
    return sum;
}

修改(增加)(带懒惰标记)

private int[] b;
// 数组b存储懒惰标记
public void update(int l, int r, int c, int s, int t, int p){
    // l,r为修改区间,c为修改量,[s,t]为当前节点包含的区间,p为当前节点的编号
    if (l <= s && t <= r){
        d[p] += (t-s+1)*c;
        b[p] += c;
    }
    int m = s + ((t-s) >> 1);
    if (b[p] && s != t) {
        // 如果当前节点的懒惰标记非空,则更新当前节点两个字节点的值和懒惰标记值
        d[p * 2] += b[p] * (m-s+1);
        d[p * 2 + 1] += b[p] * (t-m);
        b[p * 2] += b[p];
        b[p * 2 + 1] += b[p];
        b[p] = 0; // 当前节点的懒惰标记值清零
    }
    if (l <= m) update(l,r,c,s,m,p*2);
    if (r > m) update(l,r,c,m+1,t,p*2+1);
    d[p] = d[p*2] + d[p*2+1];
}

查询(带懒惰标记)

public int getSum(int l, int r, int s, int t, int p){
    if (l <= s && t <= r) return d[p];
    int m = s + ((t-s) >> 1);
    if (b[p]) {
        // 这里不用判断是否是子节点,因为上面查询环节会直接返回值
        d[p*2] += b[p] * (m-s+1);
        d[p*2+1] += b[p] * (t-m);
        b[p*2] += b[p];
        d[p*2+1] += b[p];
        b[p] = 0;
    }
    int sum = 0;
    if (l <= m) sum += getSum(l,r,s,m,p*2);
    if (r > m) sum += getSum(l,r,m+1,t,p*2+1);
    
    return sum;
}

修改(赋值)(带懒惰标记)

void update(int l, int r, int c, int s, int t, int p) {
    if (l <= s && t <= r) {
        d[p] = (t-s+1) *c, b[p] = c,v[p] = 1;
        return ;
    }
    int m = s + ((t-s) >> 1);
    if (v[p]) {
        d[p*2] = b[p] * (m-s+1);
        d[p*2+1] = b[p] * (t-m);
        b[p*2] = b[p*2=1] = b[p];
        v[p*2] = v[p*2+1] = 1;
        v[p] = 0;
    }
    if (l <= m) update(l,r,c,s,m,p*2);
    if (r>m)update(l,r,c,m+1,t,p*2+1);
}

public int getSum(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return d[p];
    int m = s + ((t-s) >> 1);
    if (v[p]){
        d[p * 2] += d[p] * (s-m+1);
        d[p*2+1] += d[p] *(t-m);
        b[p*2] = b[p*2+1] = b[p];
        v[p*2] = v[p*2+1] = 1;
        v[p] = 0;
    }
    int sum = 0;
    if(l <= m) sum = getSum(l, r, s, m, p*2);
    if (r > m) sum += getSum(l,r,m,t,p*2+1);
    return sum;
}