is there a cheap/easy way to get sub O(N) performance, using the out-of-the-box functionality of perl?

No. It is possible to do o(N) queries, but only after ω(N) pre-processing time. That's independent of the language.

Further, I would like to be able to update the array (insert elements in the middle) with minimal cost.

If you mean by "updating", "adding more elements", using a traditional Perl array, it takes linear time.