LG 4514 上帝造题的七分钟

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转此题卡常,需要使用二维树状数组联想一维的树状数组:差分数组:$d_0=a_0,d_i=ai-a{i-1}(i>0)$令差分数组的前缀和$sdi=\sum{j=0}^id_j$,那么$sd_i=a_i$我们现在来看看二维前缀和$s(i,j)=s(i-1,j)+s(i,j-1)-s(i-1,j-1)+a(i,j)$查询$(x_1,y_1)$到$(x_2,y_2)$的和则为:$s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)+s(x_1-1,y_1-1)$我们可以使用差分数组……