Mo's algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /mo-algorithm#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /mo-algorithm#noredirect を利用してください。
name
Mo's algorithm
short description
Mo's algorithm とは、群 $G$ の要素の列 $(a_0, a_1, \dots, a _ {N-1})$ と区間の列 $\lbrack l_0, r_0), \lbrack l_1, r_1), \dots, \lbrack l _ {Q-1}, r _ {Q-1})$ が与えられたとき、それぞれの区間中の要素の総和 $\sum _ {i \in \lbrack l_j, r_j)} a_i$ を全体で $O(N \sqrt{Q})$ あるいは $O((N + Q) \sqrt{N})$ で求めるアルゴリズムである。ただし、その計算の過程において、群の演算 $\cdot$ が要素 $A \in G$ と添字 $i$ に対し $A \cdot a_i, A \cdot a_i^{-1}, a_i \cdot A, a_i^{-1} \cdot A$ のいずれかの形でしか出現しないという特徴がある。