luckydenis · luckydenis · Mar 8, 2021 · Mar 8, 2021
diff --git a/README.md b/README.md
@@ -22,12 +22,14 @@
 * [Сортировка подсчетом](./notes/ru/sorting/counting.md)
 * [Быстрая сортировка](./notes/ru/sorting/quick_sort.md)
 * [Сортировка слиянием](./notes/ru/sorting/merge_sort.md)
+* [Подсчет инверсий без использования Таблицы Инверсий](./notes/ru/sorting/count_inversion_not_use_table.md)
 
 #### Графы
 * [Обход графа в глубину](./notes/ru/graph/depth.md)
 * [Обход графа в ширину](./notes/ru/graph/breadth.md)
 * [Поиск кротчайшего пути. Алгоритм Дейкстры](./notes/ru/graph/dijkstra.md)
-* [Наименьший общий предок для бинарного дерева. LCA](notes/ru/graph/lca_for_bin_tree.md)
+* [Наименьший общий предок для дерева. LCA](./notes/ru/graph/lca.md)
+* [Наименьший общий предок для бинарного дерева. LCA](./notes/ru/graph/lca_for_bin_tree.md)  
 * [Проверка наличия цикла в графе](./notes/ru/graph/find_graph_loop.md)
 * [Топологическая сортировка](./notes/ru/graph/topological_sort.md)
 

diff --git a/notes/ru/graph/lca.md b/notes/ru/graph/lca.md
@@ -0,0 +1,104 @@
+Наименьший общий предок для дерева. LCA
+-----------------------
+| [Главная](../../../README.md#Список-алгоритмов-[russian])
+| [Графы](../../../README.md#Графы)
+|
+
+> **Наименьший общий предок** (**нижайший общий предок**) вершин 
+u и v в корневом дереве T — наиболее удалённая от корня дерева 
+вершина, лежащая на обоих путях от u и v до корня, то есть 
+являющаяся предком обеих вершин. Общепринятое сокращение — 
+_LCA_ от англ. _lowest (least) common ancestor_.
+
+
+Реализация
+----------
+* #### Используя метод двойного подъема
+
+|Препроцессинг|Запросы |
+|:-----------:|:------:|
+|O(n log n)   |O(log n)|
+
+```python
+
+class Node:
+    def __init__(self, data):
+        self.data = data
+        self.left = None
+        self.right = None
+
+
+bin_tree_root = Node(1)
+bin_tree_root.left = Node(2)
+bin_tree_root.left.left = Node(3)
+bin_tree_root.left.left.left = Node(5)
+bin_tree_root.left.right = Node(4)
+bin_tree_root.right = Node(6)
+bin_tree_root.right.left = Node(7)
+bin_tree_root.right.right = Node(8)
+bin_tree_root.right.right.left = Node(9)
+
+
+def dfs(start):
+    stack = [start]
+    dist = dict()
+    parent = dict()
+    dist[start.data] = 0
+    parent[start.data] = start.data
+    n = 0
+    max_h = 0
+    while stack:
+        n += 1
+        v = stack.pop()
+        if max_h < dist[v.data]:
+            max_h = dist[v.data]
+
+        if v.left:
+            stack.append(v.left)
+            dist[v.left.data] = dist[v.data] + 1
+            parent[v.left.data] = v.data
+        if v.right:
+            stack.append(v.right)
+            dist[v.right.data] = dist[v.data] + 1
+            parent[v.right.data] = v.data
+
+    return parent, dist, n, max_h
+
+
+def preprocess(root):
+    p, d, n, max_h = dfs(root)
+
+    dp = dict()
+    for i in range(1, n + 1):
+        if i not in dp:
+            dp[i] = []
+        dp[i].append(p[i])
+
+    for j in range(1, max_h):
+        for i in range(1, n + 1):
+            dp[i].append(dp[p[i]][j - 1])
+
+    return dp, d, p, max_h
+
+
+def lca(v, u, dp, d, p, max_h):
+    if d[v] > d[u]:
+        v, u = u, v
+
+    for i in range(max_h - 1, -1, -1):
+        if d[dp[u][i]] - d[v] >= 0:
+            u = dp[u][i]
+
+    if v == u:
+        return v
+
+    for i in range(max_h - 1, -1, -1):
+        if dp[v][i] != dp[u][i]:
+            v = dp[v][i]
+            u = dp[u][i]
+
+    return p[v]
+
+
+print(lca(5, 4, *preprocess(bin_tree_root))) # 2
+```
diff --git a/notes/ru/graph/lca_for_bin_tree.md b/notes/ru/graph/lca_for_bin_tree.md
@@ -1,4 +1,4 @@
-Наименьший общий предок для бинарного дерева. LCA
+Наименьший общий предок для дерева. LCA
 -----------------------
 | [Главная](../../../README.md#Список-алгоритмов-[russian])
 | [Графы](../../../README.md#Графы)
@@ -13,92 +13,42 @@ _LCA_ от англ. _lowest (least) common ancestor_.
 
 Реализация
 ----------
-* #### Используя метод двойного подъема
+* #### Используя рекурсию
 
-|Препроцессинг|Запросы |
-|:-----------:|:------:|
-|O(n log n)   |O(log n)|
+|Запросы |
+|:------:|
+|O(log n)|
 
 ```python
-
 class Node:
     def __init__(self, data):
         self.data = data
         self.left = None
         self.right = None
 
 
-bin_tree_root = Node(1)
-bin_tree_root.left = Node(2)
-bin_tree_root.left.left = Node(3)
-bin_tree_root.left.left.left = Node(5)
-bin_tree_root.left.right = Node(4)
-bin_tree_root.right = Node(6)
-bin_tree_root.right.left = Node(7)
-bin_tree_root.right.right = Node(8)
-bin_tree_root.right.right.left = Node(9)
-
-
-def dfs(start):
-    stack = [start]
-    d = dict()
-    p = dict()
-    d[start.data] = 0
-    p[start.data] = start.data
-    n = 0
-    max_h = 0
-    while stack:
-        n += 1
-        v = stack.pop()
-        if max_h < d[v.data]:
-            max_h = d[v.data]
-
-        if v.left:
-            stack.append(v.left)
-            d[v.left.data] = d[v.data] + 1
-            p[v.left.data] = v.data
-        if v.right:
-            stack.append(v.right)
-            d[v.right.data] = d[v.data] + 1
-            p[v.right.data] = v.data
-
-    return p, d, n, max_h
-
-
-def preprocess(root):
-    p, d, n, max_h = dfs(root)
-
-    dp = dict()
-    for i in range(1, n + 1):
-        if i not in dp:
-            dp[i] = []
-        dp[i].append(p[i])
-
-    for j in range(1, max_h):
-        for i in range(1, n + 1):
-            dp[i].append(dp[p[i]][j - 1])
-
-    return dp, d, p, max_h
-
-
-def lca(v, u, dp, d, p, max_h):
-    if d[v] > d[u]:
-        v, u = u, v
-
-    for i in range(max_h - 1, -1, -1):
-        if d[dp[u][i]] - d[v] >= 0:
-            u = dp[u][i]
-
-    if v == u:
-        return v
+bin_tree_root = Node(10)
+bin_tree_root.left = Node(8)
+bin_tree_root.left.left = Node(7)
+bin_tree_root.left.left.left = Node(6)
+bin_tree_root.left.right = Node(9)
+bin_tree_root.right = Node(12)
+bin_tree_root.right.left = Node(11)
+bin_tree_root.right.right = Node(14)
+bin_tree_root.right.right.left = Node(13)
 
-    for i in range(max_h - 1, -1, -1):
-        if dp[v][i] != dp[u][i]:
-            v = dp[v][i]
-            u = dp[u][i]
 
-    return p[v]
+def lca(node, lt, rt):
+    if lt < node.data and rt < node.data:
+        return lca(node.left, lt, rt)
+    if lt > node.data and rt > node.data:
+        return lca(node.right, lt, rt)
+    if lt == node.data or rt == node.data:
+        return node.data
+    return node.data
 
 
-print(lca(5, 4, *preprocess(bin_tree_root))) # 2
+print(lca(bin_tree_root, 11, 13)) # 12
+print(lca(bin_tree_root, 6, 9)) # 8
+print(lca(bin_tree_root, 6, 13)) # 10
 ```
diff --git a/notes/ru/sorting/count_inversion_not_use_table.md b/notes/ru/sorting/count_inversion_not_use_table.md
@@ -0,0 +1,57 @@
+Подсчет инверсий без использования Таблицы Инверсий.
+----------------
+| [Главная](../../../README.md#Список-алгоритмов-[russian])
+| [Сортировки](../../../README.md#Сортировки)
+|
+
+> **Число инверсии** — это мощность множества инверсии. 
+Это общепринятая мера сортировки перестановки или 
+последовательности.
+
+
+Реализация
+----------
+|Лучшее время|Среднее время|Худшее время    |Память   |Устойчивая|Обмены в среднем|
+|:----------:|:-----------:|:--------------:|:-------:|:--------:|:--------------:|
+|O(n log n)  |O(n log n)   |O(n log n)      |O(log n) |+         |O(n log n)      |
+
+```python
+cnt = 0
+
+
+def merge_sort(arr):
+    global cnt
+    if len(arr) <= 1:
+        return
+
+    left = arr[:len(arr) // 2]
+    right = arr[len(arr) // 2:]
+    merge_sort(left)
+    merge_sort(right)
+
+    i, j, k = 0, 0, 0
+    while i < len(left) and j < len(right):
+        if left[i] < right[j]:
+            arr[k] = left[i]
+            i += 1
+        else:
+            arr[k] = right[j]
+            cnt += len(left) - i
+            j += 1
+        k += 1
+
+    while i < len(left):
+        arr[k] = left[i]
+        i += 1
+        k += 1
+
+    while j < len(right):
+        arr[k] = right[j]
+        j += 1
+        k += 1
+
+
+nums = [5, 4, 2, 1]
+merge_sort(nums)
+print(cnt) # 6
+```