A range-sum query sums over all selected cells of an OLAP data cube where the selection is specified by ranges of contiguous values for each dimension. An efficient approach to process such queries is to precompute a prefix cube (PC), which is a cube of the same dimensionality and size as the original data cube but with a prefix range-sum stored in each cell. Using a PC, any range-sum query can be evaluated at a cost that is independent of the size of the sub-cube circumscribed by the query. However, a drawback of PCs is that they are very costly to maintain. Recently, a variant of prefix cubes called Relative Prefix Cubes (RPC) has been proposed to alleviate this problem. In this paper, we propose a new class of cube representations called Hierarchical Cubes, which is based on a design framework defined by two orthogonal dimensions. Our results show that a particular cube design called the Hierarchical Band Cube (HBC) is the overall winner: it not only has a significantly better query-update tradeoff than previous approaches, but it can also be more effectively buffered.