  In this paper, we introduce the \emph{interval query problem} on cube-free
median graphs. Let $G$ be a cube-free median graph and $\mathcal{S}$ be a
commutative semigroup. For each vertex $v$ in $G$, we are given an element
$p(v)$ in $\mathcal{S}$. For each query, we are given two vertices $u,v$ in $G$
and asked to calculate the sum of $p(z)$ over all vertices $z$ belonging to a
$u-v$ shortest path. This is a common generalization of range query problems on
trees and grids. In this paper, we provide an algorithm to answer each interval
query in $O(\log^2 n)$ time. The required data structure is constructed in
$O(n\log^3 n)$ time and $O(n\log^2 n)$ space. To obtain our algorithm, we
introduce a new technique, named the \emph{stairs decomposition}, to decompose
an interval of cube-free median graphs into simpler substructures.
