It should be effective to avoid linear search and also should be small. Binary Indexed Tree might be a good choice.