论文标题
间隔查询问题，无数立方体中值图
Interval Query Problem on Cube-free Median Graphs
论文作者
论文摘要
在本文中，我们在无立方的中间图上介绍了\ emph {Interpal查询问题}。令$ g $为无立方体的中间图，$ \ Mathcal {s} $为交换性半群。对于$ g $中的每个顶点$ v $，我们将获得一个元素$ p（v）$中的$ \ \ \ m rathcal {s} $。对于每个查询，我们都会给出两个顶点$ u，v $ in $ g $，并要求计算属于$ u-u-v $最短路径的所有顶点$ z $上的$ p（z）$的总和。这是对树木和网格上的范围查询问题的普遍概括。在本文中，我们提供了一种算法来回答$ O（\ log^2 n）$时间的每个间隔查询。所需的数据结构以$ O（n \ log^3 n）$时间和$ O（n \ log^2 n）$ space构建。为了获得我们的算法，我们引入了一种名为\ emph {stairs Decomposition}的新技术，以将无立方值图的间隔分解为更简单的子结构。
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.
