k=4;   % number of points, as a power of 2.
n=2^k; % power of 2 not strictly necessary but cleaner

x=1:n; % example input data

s=x;   %% subcube sum

p=x;   %% subcube prefix

for i=1:k
   %% a matlab trick, not to be used in real computing probably
   %% reshape inefficient but convenient
   %% ith dimension recast as second of three
   s = reshape(s, 2.^[i-1 1 k-i]);
   p = reshape(p, 2.^[i-1 1 k-i]);

   t = s(:,1,:); s(:,1,:) = sum(s,2); s(:,2,:) = s(:,2,:)+t;

   p(:,2,:) = p(:,2,:)+t;
end

p(:)'
