Is it possible to do simple arithmetic (e.g. addition) on "compressed" integers?

I would like to compress an an array of integers, initially initialized to 0, using a yet-to-be-determined integer compression/decompression method.

Is it possible with some integer compression method to increment (+1) a specific element of an array of 开发者_运维问答compressed integers accurately using C or C++?

---

Of all the common compression techniques, two stand out as potentially usable in this without a full decompress cycle.

First, sparse arrays were built specifically for this. With a sparse array, you typically store a map of index to value. You don't store array elements that haven't been modified, so if most of your array is 0, it need not be stored. Many arrays (and matrices) in simulations are sparse, and there's a huge literature. Here adding to a value would simply be accessing the index with [] and incrementing - the access will create if nonexistent.

Next, run length encoding may also work if you find that you are working with large sequences of the same number, but those "runs" are not all the same number. Since they are not the same, a sparse array would not work and RLE is a solution. Incrementing a number is not as easy as for sparse, but basically if not a run, you add and check to see if you can make a new run. If part of a run, you split the run. RLE typically only makes sense with visual data or certain mathematical patterns.

---

You can certainly implement this, if your increment method:

1. Decompresses the entire array.
2. Increments the desired entry.
3. Compresses the entire array again.

If you want to increment in less of a dumb way you'll need intimate knowledge of the compression process, and so would we to give you more assistance.