This question came up in Chat the other day. Here is the solution that I came up with. I'll be interested if it can be beaten.

banded[n_Integer?EvenQ] :=
  With[
   {main = RandomReal[99, n - 1],
    side = SparseArray[{}, n - 2, -0.5]},
   SparseArray[{i_, i_} :> main[[i]], n - 1] +
    Sum[side ~DiagonalMatrix~ i, {i, {-1, 1}}]
  ]

This uses several tricks and observations. Credit for the first goes to Norbert Pozar, who showed me that this is a very fast way to construct a diagonal SparseArray from a list x:

SparseArray[{i_, i_} :> x[[i]], Length @ x]

The second is my own observation that a DiagonalMatrix made from a SparseArray list is also created quickly. This in enhanced by creating the list with SparseArray[{}, n - 2, -0.5], where the "background" of the array is the element to be repeated, rather than ConstantArray or Table. One can see below that only minimal evaluation takes place:

SparseArray[{}, 10^6, -0.5] // InputForm

SparseArray[Automatic, {1000000}, -0.5, {1, {{0, 0}, {}}, {}}]

DiagonalMatrix is particularly fast with this input form.

These "tricks" are combined with the knowledge that adding sparse SparseArrays is fast, and that Band can be rather slow (again thanks to Norbert Pozar) to create a solution that is about fifty times faster than the original.

This question came up in Chat the other day. Here is the solution I proposed.

banded[n_Integer?EvenQ] :=
  With[
   {main = RandomReal[99, n - 1],
    side = SparseArray[{}, n - 2, -0.5]},
   SparseArray[{i_, i_} :> main[[i]], n - 1] +
    Sum[side ~DiagonalMatrix~ i, {i, {-1, 1}}]
  ]

This uses several tricks and observations. Credit for the first goes to Norbert Pozar, who showed me that this is a very fast way to construct a diagonal SparseArray from a list x:

SparseArray[{i_, i_} :> x[[i]], Length @ x]

The second is my own observation that a DiagonalMatrix made from a SparseArray list is also created quickly. This in enhanced by creating the list with SparseArray[{}, n - 2, -0.5], where the "background" of the array is the element to be repeated, rather than ConstantArray or Table. One can see below that only minimal evaluation takes place:

SparseArray[{}, 10^6, -0.5] // InputForm

SparseArray[Automatic, {1000000}, -0.5, {1, {{0, 0}, {}}, {}}]

DiagonalMatrix is particularly fast with this input form.

These "tricks" are combined with the knowledge that adding sparse SparseArrays is fast, and that Band can be rather slow (again thanks to Norbert Pozar) to create a solution that is about fifty times faster than the original.