数据结构补完计划

建树：

void build(int l, int r, int o){
    t[o].l = l;t[o].r = r;
    if(l == r){
        t[o].val = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, o<<1);
    build(mid+1, r, o<<1|1);
    t[o].val = t[o<<1].val + t[o<<1|1].val;
}

区间加：

void pushdown(int o){
	if(t[o].add){
		t[o<<1].val += t[o].add * (t[o<<1].r - t[o<<1].l + 1);
		t[o<<1|1].val += t[o].add * (t[o<<1|1].r - t[o<<1|1].l + 1);
		t[o<<1].add += t[o].add;
        t[o<<1|1].add += t[o].add;
        t[o].add = 0;
	}
	return ;
}

void add(int o, int l, int r, int val){
    if(l <= t[o].l&&t[o].r <= r){//当前区间被包含
        t[o].add += w;
        t[o].val += (t[o].r - t[o].l + 1) * w;
        return ;
    }
    pushdown(o);
    int mid = (t[o].l + t[o].r) >> 1;
    if(l <= mid) add(o<<1, l, r, w);
	if(mid+1 <= r) add(o<<1|1, l, r, w);
	t[o].val = t[o<<1].val + t[o<<1|1].val;
}

区间和查询：

ll ask(int l, int r, int o){
    if(t[o].l >= l && t[o].r <= r){
        return t[o].val;
    }
    pushdown(o);
    ll sum = 0;
    int mid = (t[o].l + t[o].r) >> 1;
    if(l <= mid) sum += ask(l, mid, o<<1);
    if(mid+1 <= r) sum += ask(mid+1, r, o<<1|1);
    return sum;
}