*Inspired by people losing their mind over dp[mask][-1] here...*

#### Motivation

Sometimes you need to implement an array with negative indices. For example you may want to have an array `dp[i]`

which stores values for all $$$i$$$, $$$-10^5 \le i \le 10^5$$$. One way is to make `dp`

an (unordered) map. But this is slow and can get TLE in certain problems. Another way is this:

```
const int MAX_N = 2e5 + 20;
const int ZERO = 1e5 + 5;
int dp [MAX_N];
```

and instead of calling `dp[i]`

you call `dp[ZERO + i]`

. If I want to access `dp[-5]`

for example, I access `dp[ZERO - 5]`

. But this is tedious and error-prone. It's very easy to make a mistake by forgetting to write `ZERO`

somewhere.

#### The solution

Do the above, but do it like this!

```
const int MAX_N = 2e5 + 20;
const int ZERO = 1e5 + 5;
int dp_ [MAX_N];
int& dp (int idx) { // the '&' is very important!
return dp_[ZERO + idx];
}
```

A very important part is that `dp`

doesn't return an `int`

; it returns an `int&`

— a *reference* to the given position in the array. This means that it's very convenient to use. We can assign to `dp(i)`

, modify `dp(i)`

etc.

```
int main () {
int main () {
dp(-300) = 7;
dp(40) = 5;
dp(-300) += 777; // All of those are fine!
cout << dp(40) << " " << dp(-300) << endl;
swap(dp(40), dp(-300)); // Even this works!
cout << dp(40) << " " << dp(-300) << endl;
}
```

I bet many people do know that.

Your method is very dangerous because it's very easy to just type

`dp[i]`

somewhere (instead of`dp(i)`

)~~and it will compile~~. EDIT: -is-this-fft- is right below that this mistake won't compile but I will still claim that it's very inconvenient to use`dp(i)`

and I would keep writing it wrong way all the time.Instead, in the middle of an array save a new pointer that will pretend to be a new array:

I use

`dp_`

as the array name for this exact reason. Typing`dp[i]`

results in something like`error: cannot convert ‘int’ to ‘int&(int)’ in assignment`

.Second that. Trick from original post is very dangerous, it's literally shooting ourselves in a foot, while method mentioned by Errichto is much much better. (EDIT: Ahhh, I now see the above OP's response, I guess it is fine in that case)

Follow-up question: how to make multi-dimensional array with range [-M..M][-M..M][-M..M]?

I always used a complicated struct for that, where I would implement

`[]`

operator.It is possible to do this with similar trick to yours, just much more complicated. Resulting type will contain a lot of & and *, but I was never good with these things :p. C++ magicians (at least from my point of view) are required here.

Theoretically you can do the same — put a pointer into the center of array. You just need to typecast it, if your array has more than one dimension. I'm sure that C++ standard looks bad at this kind of casts, so some unobvious pitfalls can arise.

`MyArray<int> dp(2 * n, m)`

creates a vector with 2n elements, where i-th element has index i-m. It is possible to create multi-dimensional vectors, just like normal vectors: examplethis is beyond geniosity

Just wondering but will the pointer method be slower than adding an offset manually, like for example if u access the array many times? Because i heard pointers take up more time, so yea just curious. Thanks in advance.

A pointer is an integer (which happens to contain a memory address) and arithmetic on it doesn't work much differently.$$$\textrm{}^{\dagger}$$$ Both approaches dereference only once. The method in the original post has the additional overhead of a function call, but we can expect the compiler to inline it since it's so short.

$$$^{\dagger}$$$ Note that a[i] or *(a + i) is going to involve multiplication, since the correct address is that of a plus i * sizeof(datatype).

There is a similar trick when you have a problem about some matrix (like "find the shortest path in a labirint etc"), and you want to work with pairs so that you won't need to mess up with double indices.

You can write:

And now it's pretty simple to manage any kind of dfs:

I used negative index in vector today in this solution. (search for prefix[-2])

Later I read about why it was working. Coincidentally on the same day I come across this post now.