4. Given an integer $n \geqslant 2$. Let $n$ non-empty finite sets $A_{1}, A_{2}, \cdots, A_{n}$ satisfy:
$$
\left|A_{i} \Delta A_{j}\right|=|i-j|(i, j \in\{1,2, \cdots, n\}),
$$

where
$$
X \Delta Y=\{a \mid a \in X, a \notin Y\} \cup\{a \mid a \in Y, a \notin X\} .
$$

Find the minimum value of $\left|A_{1}\right|+\left|A_{2}\right|+\cdots+\left|A_{n}\right|$.
4. For integer $n \geqslant 2$, prove that for any positive integer $k$,
$$
S_{2 k} \geqslant k^{2}+2, S_{2 k+1} \geqslant k(k+1)+2 \text {. }
$$

First, give two obvious conclusions:
(1) For finite sets $X$ and $Y$,
$$
|X|+|Y| \geqslant|X \Delta Y| \text {. }
$$
(2) If non-empty finite sets $X$ and $Y$ satisfy $|X \Delta Y|=1$, then $|X|+|Y| \geqslant 3$.
(Indeed, if not, then $|X|=|Y|=1$, thus, $|X \Delta Y|=0$ or 2, which is a contradiction.)
When $n=2 k$, by the condition and conclusion (1),
$$
\begin{array}{l}
\left|A_{i}\right|+\left|A_{2 k+1-i}\right| \geqslant\left|A_{i} \Delta A_{2 k+1-i}\right| \\
=2 k+1-2 i(i=1,2, \cdots, k-1) . \\
\text { Also, }\left|A_{k} \Delta A_{k+1}\right|=1 \text { and conclusion (2) give } \\
\left|A_{k}\right|+\left|A_{k+1}\right| \geqslant 3 \\
\Rightarrow S_{2 k}=\left|A_{k}\right|+\left|A_{k+1}\right|+\sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+1-i}\right|\right) \\
\geqslant 3+\sum_{i=1}^{k-1}(2 k+1-2 i)=k^{2}+2 .
\end{array}
$$

Similarly, when $n=2 k+1$, we have
$$
\begin{array}{l}
\left|A_{i}\right|+\left|A_{2 k+2-i}\right| \geqslant\left|A_{i} \Delta A_{2 k+2-i}\right| \\
=2 k+2-2 i(i=1,2, \cdots, k-1), \\
\left|A_{k}\right|+\left|A_{k+1}\right| \geqslant 3,\left|A_{k+2}\right| \geqslant 1 \\
\Rightarrow S_{2 k+1}=\left|A_{k}\right|+\left|A_{k+1}\right|+\left|A_{k+2}\right|+ \\
\sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+2-i}\right|\right) \\
\geqslant 4+\sum_{i=1}^{k-1}(2 k+2-2 i) \\
=k(k+1)+2 .
\end{array}
$$

And $\left|A_{k}\right|+\left|A_{k+1}\right| \geqslant 3,\left|A_{k+2}\right| \geqslant 1$
$$
\begin{aligned}
\Rightarrow & S_{2 k+1}=\left|A_{k}\right|+\left|A_{k+1}\right|+\left|A_{k+2}\right|+ \\
& \sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+2-i}\right|\right) \\
& \geqslant 4+\sum_{i=1}^{k-1}(2 k+2-2 i) \\
= & k(k+1)+2 .
\end{aligned}
$$

On the other hand, take the sets $A_{1}, A_{2}, \cdots, A_{2 k+1}$ as follows:
$$
\begin{array}{l}
A_{i}=\{i, i+1, \cdots, k\}(i=1,2, \cdots, k), \\
A_{k+1}=\{k, k+1\}, \\
A_{k+j}=\{k+1, k+2, \cdots, k+j-1\}(j=2,3, \cdots, k+1) .
\end{array}
$$

For this set of sets, it is easy to verify that $\left|A_{i} \Delta A_{j}\right|=|i-j|$ for any $i, j \in\{1,2, \cdots, 2 k+1\}$.
At this point, after calculation, we get
$$
\begin{array}{l}
S_{2 k+1}=\frac{k(k+1)}{2}+2+\frac{k(k+1)}{2} \\
=k(k+1)+2 .
\end{array}
$$

When taking the first $2 k$ sets, we get
$$
S_{2 k}=S_{2 k+1}-k=k^{2}+2 \text {. }
$$

In summary, the minimum value of $S_{n}$ is $\left[\frac{n^{2}}{4}\right]+2$, where $[x]$ denotes the greatest integer not exceeding the real number $x$.