树状数组小结

树状数组小结"/>

树状数组小结

树状数组就两种情况，每次更新一个点，最后的时候统计一个区间，或者每次更新一个区间，最后统计某个点

然后有个图可以帮助我们理解:

就是这个 

 每个节点的管辖范围是他的左子树  然后和 树状数组是对应的

这张图是百度上的

然后模板：

一维模板：

inline int lowbit( int x ){return x & ( -x );
}void updata( int x, int val ){while( x <= N ){sum[x] += val;x += lowbit( x );}
}int getsum( int x ){int ans = 0;while( x > 0 ){ans += sum[x];x -= lowbit( x );}return ans;
}

inline int lowbit( int x ){return x & ( -x );
}void updata( int x, int y, int val ){for( int i = x; i <= N; i += lowbit( i ) ){for( int j = y; j <= N; j += lowbit( j ) ){sum[i][j] = ( sum[i][j] + val ) % 2;}}
}int getsum( int x, int y ){int ans = 0;for( int i = x; i > 0; i -= lowbit( i ) ){for( int j = y; j > 0; j -= lowbit( j ) ){ans = ( sum[i][j] + ans ) % 2;}}return ans;
}