Задача: 315. Count of Smaller Numbers After Self
Сложность: hard

Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].

Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

👨‍💻 Алгоритм:

1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.

2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.

3⃣Верните результат.

😎 Решение:

class Solution {
    func countSmaller(_ nums: [Int]) -> [Int] {
        let offset = 10000 
        let size = 2 * 10000 + 1
        var tree = [Int](repeating: 0, count: size * 2)
        var result = [Int]()
        
        for num in nums.reversed() {
            let smallerCount = query(0, num + offset, tree, size)
            result.append(smallerCount)
            update(num + offset, 1, tree, size)
        }
        
        return result.reversed()
    }

    private func update(_ index: Int, _ value: Int, _ tree: inout [Int], _ size: Int) {
        var idx = index + size
        tree[idx] += value
        while idx > 1 {
            idx /= 2
            tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
        }
    }

    private func query(_ left: Int, _ right: Int, _ tree: [Int], _ size: Int) -> Int {
        var result = 0
        var l = left + size 
        var r = right + size
        while l < r {
            if l % 2 == 1 {
                result += tree[l]
                l += 1
            }
            l /= 2
            if r % 2 == 1 {
                r -= 1
                result += tree[r]
            }
            r /= 2
        }
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний