function Ubar = NRTpsums(Sbar, N)
% Octave/MATLAB function to compute partial sums
% along paths in a non-recombining tree (NRT).
% INPUTS:                               (Example)
%   Sbar = NRT array of length 2*2^N-1     (1:15)
%   N = tree depth, must be >=0               (3)
% OUTPUT:
%   Ubar = NRT of partial sums, same size as Sbar
% EXAMPLE:
%  Ubar = NRTpsums(1:15,3)
%
  Ubar=zeros(size(Sbar)); % allocate the output
  Ubar(1)=Sbar(1);  % trivial first partial sum
  for m=1:2^N-1   % all future times up to N-1
    Ubar(2*m)=Ubar(m)+Sbar(2*m);     % down
    Ubar(2*m+1)=Ubar(m)+Sbar(2*m+1); % up
  end
  return
end
