Protein structure analysis is a very important research topic in the molecular biology of the post-genomic era. The root mean square deviation (RMSD) is the most frequently used measure for comparing two protein three-dimensional (3-D) structures. In this paper, we deal with two fundamental problems related to the RMSD. We first deal with a problem called the "range RMSD query" problem. Given an aligned pair of structures, the problem is to compute the RMSD between two aligned substructures of them without gaps. This problem has many applications in protein structure analysis. We propose a linear-time preprocessing algorithm that enables constant-time RMSD computation. Next, we consider a problem called the "substructure RMSD query" problem, which is a generalization of the above range RMSD query problem. It is a problem to compute the RMSD between any substructures of two unaligned structures without gaps. Based on the algorithm for the range RMSD problem, we propose an O(nm) preprocessing algorithm that enables constant-time RMSD computation, where n and m are the lengths of the given structures. Moreover, we propose O(nm log r/r)-time and O(nm/r)-space preprocessing algorithm that enables O(r) query, where r is an arbitrary integer such that 1 < or = r < or = min(n, m). We also show that our strategy also works for another measure called the unit-vector root mean square deviation (URMSD), which is a variant of the RMSD.