动态开点线段树实现区间和

void pushdown(int p, int l, int r)
{
	int mid = l + r >> 1;
	if (!ls[p]) ls[p] = ++tot;
	if (!rs[p]) rs[p] = ++tot;
	sum[ls[p]] += (mid - l + 1) * lazy[p];
	sum[rs[p]] += (r - mid) * lazy[p];
	lazy[ls[p]] += lazy[p];
	lazy[rs[p]] += lazy[p];
	lazy[p] = 0;
}

void modify(int &p, int l, int r, int x, int y, int val)
{
	if (!p) p = ++tot;
	if (lazy[p]) pushdown(p, l, r);
	if (x <= l && y >= r)
	{
		sum[p] = (r - l + 1) * val;
		lazy[p] += val;
		return;
	}
	int mid = l + r >> 1;
	if (x <= mid)modify(ls[p], l, mid, x, y, val);
	if (y > mid)modify(rs[p], mid + 1, r, x, y, val);
	sum[p] = sum[ls[p]] + sum[rs[p]];
}

ll query(int &p,int l,int r,int x,int y)
{
	if (!p) return 0;
	if (lazy[p]) pushdown(p,l,r);
	if (x <= l && y >= r) return sum[p];
	int mid = l + r >> 1;
	ll ans = 0;
	if (x <= mid)ans += query(ls[p],l,mid,x,y);
	if (y > mid)ans += query(rs[p],mid+1,r,x,y);
	return ans;
}