MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size integer array, along an index that maps each substring to the appropriate position of the array. This index has size $1+2+..+n= O(n^2)$. So why the storage cost it is said to be $O(n)$ at the textbooks?
You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.
You store only the position of suffixes in the index, not the suffixes themselves.
So the storage complexity is O(n) for the index. You then have to keep the original string along with the suffixes array. The original string storage complexity is O(n) also by definition.
The whole storage complexity remains O(n).