二维树状数组

xiaoxiao2021-02-28  113

是一维树状数组的扩充,修改和查询的复杂度均为log^2(n). 空间复杂度略大 n^2

void add(int x,int y,int d) { int i,j; for(i=x;i<N;i+=lowbit(i)) for(j=y;j<N;j+=lowbit(j)) mat[i][j]+=d; } LL sum(int x,int y) { LL res=0; int i,j; for(i=x;i>0;i-=lowbit(i)) for(j=y;j>0;j-=lowbit(j)) res+=mat[i][j]; return res; }

转载请注明原文地址: https://www.6miu.com/read-62113.html

最新回复(0)