'saNaiveとsaDoublingを高速化。しきい値調整。'

NASU41 · Sep 21, 2020 · Sep 20, 2020 · Sep 20, 2020 · Sep 20, 2020 · Sep 20, 2020
commit 0123f59f5909e7a212f19356ac5c62d762e46058
diff --git a/StringAlgorithm/StringAlgorithm.java b/StringAlgorithm/StringAlgorithm.java
@@ -18,7 +18,7 @@ private static int[] saNaive(int[] s) {
 		return sa;
 	}
 
-	public static int[] saDoubling(int[] s) {
+	private static int[] saDoubling(int[] s) {
 		int n = s.length;
 		int[] sa = new int[n];
 		for(int i = 0;i < n;i++){
@@ -36,7 +36,7 @@ public static int[] saDoubling(int[] s) {
 				int ry = y + _k < n ? _rnk[y + _k] : -1;
 				return rx - ry;
 			};
-			insertionsortUsingComparator(sa, cmp);
+			mergesortUsingComparator(sa, cmp);
 			tmp[sa[0]] = 0;
 			for (int i = 1; i < n; i++) {
 				tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.applyAsInt(sa[i - 1], sa[i]) < 0 ? 1 : 0);
@@ -63,8 +63,33 @@ private static void insertionsortUsingComparator(int[] a, java.util.function.Int
 		}
 	}
 
-	private static final int THRESHOLD_NAIVE = 10;
-	private static final int THRESHOLD_DOUBLING = 40;
+	private static void mergesortUsingComparator(int[] a, java.util.function.IntBinaryOperator comparator) {
+		final int n = a.length;
+		final int[] work = new int[n];
+		for (int block = 1; block <= n; block <<= 1) {
+			final int block2 = block << 1;
+			for (int l = 0, max = n - block; l < max; l += block2) {
+				int m = l + block;
+				int r = Math.min(l + block2, n);
+				System.arraycopy(a, l, work, 0, block);
+				for (int i = l, wi = 0, ti = m;; i++) {
+					if (ti == r) {
+						System.arraycopy(work, wi, a, i, block - wi);
+						break;
+					}
+					if (comparator.applyAsInt(work[wi], a[ti]) > 0) {
+						a[i] = a[ti++];
+					} else {
+						a[i] = work[wi++];
+						if (wi == block) break;
+					}
+				}
+			}
+		}
+	}
+
+	private static final int THRESHOLD_NAIVE = 50;
+	private static final int THRESHOLD_DOUBLING = 0;
 
 	private static int[] sais(int[] s, int upper) {
 		int n = s.length;
@@ -80,9 +105,9 @@ private static int[] sais(int[] s, int upper) {
 		if (n < THRESHOLD_NAIVE) {
 			return saNaive(s);
 		}
-		if (n < THRESHOLD_DOUBLING) {
-			return saDoubling(s);
-		}
+//		if (n < THRESHOLD_DOUBLING) {
+//			return saDoubling(s);
+//		}
 
 		int[] sa = new int[n];
 		boolean[] ls = new boolean[n];

diff --git a/out/production/AtCoderLibraryForJava/README.md b/out/production/AtCoderLibraryForJava/README.md
@@ -0,0 +1,42 @@
+# クラス FenwickTree
+
+長さ $N$ の long型配列に対し,
+
+* 要素の1点変更
+* 区間の要素の総和
+
+を $O(\log N)$ の時間で求めることができるデータ構造です.
+
+
+## コンストラクタ
+### FenwickTree
+```java
+public FenwickTree(int n)
+```
+
+長さ $n$ の配列 $a_0, a_1, \dots, a_{n-1}$を作ります. 初期値はすべて0です.
+計算量: $O(n)$
+
+```java
+public FenwickTree(long[] data)
+```
+
+長さ $n$ の配列 $a_0, a_1, \dots, a_{n-1}$を `data` により初期化します. 
+計算量: $O(n)$
+
+## メソッド
+### add
+```java
+public void add(int p, long x)
+```
+配列の第$p$要素に$x$を加える. すなわち, `a[p] += x` のこと.
+計算量: $O(\log N)$
+
+### sum
+```java
+public long sum(int l, int r)
+```
+$a_l + a_{l+1} + \dots + a_{r-1}$の値を返す. 計算量: $O(\log n)$
+
+## 使用例
+[[https://atcoder.jp/contests/practice2/submissions/16573339]]