9.一维数组前缀和
s[0]=0;
s[i]=s[i-1]+a[i];//i>=1 初始化
//l-k区间范围的和
s[k]-s[l-1];
10.二维数组前缀和
s[x][y]=s[x-1]s[y]+s[x][y-1]-s[x-1][y-1]+a[x][y];//初始化
//(x1,y1)到(x2,y2)矩阵和
s[x2][y2]-s[x1-1][y2]-s[x1][y2-1]+s[x1-1][y1-1];
9.一维数组前缀和
s[0]=0;
s[i]=s[i-1]+a[i];//i>=1 初始化
//l-k区间范围的和
s[k]-s[l-1];
10.二维数组前缀和
s[x][y]=s[x-1]s[y]+s[x][y-1]-s[x-1][y-1]+a[x][y];//初始化
//(x1,y1)到(x2,y2)矩阵和
s[x2][y2]-s[x1-1][y2]-s[x1][y2-1]+s[x1-1][y1-1];