Рейтинг: место игрока деревом Фенвика

Если ты умеешь строить дерево Фенвика по значениям и спускаться по нему к k-му элементу, листай до «Теперь сам».

Как думаешь, по чему строить дерево

Игроков 10 000, очки - от 0 до 1000, после каждой партии очки одного игрока меняются, и он смотрит своё место. Дерево Фенвика умеет сумму на префиксе и изменение элемента за log. Префикс ЧЕГО нужен для места?

Ответь себе до чтения. Если строить дерево по игрокам в каком-то порядке, префикс ничего не даст: место зависит от очков, а не от номера игрока. Нужно другое: «сколько игроков набрали не больше x очков» - это префикс по оси ОЧКОВ. Значит, позиция в дереве - не игрок, а значение очков, и по ней учитывают, сколько игроков его набрали; сама ячейка дерева Фенвика хранит сумму по отрезку значений. Тогда место = 1 + все игроки − префикс до своих очков.

На что это похоже

Табло на марафоне. Судье не нужно пересортировывать всех бегунов, когда один финишировал: достаточно знать, сколько человек пробежало быстрее. Если вести счётчик по каждой минуте финиша, ответ - сумма счётчиков до нужной минуты. Дерево Фенвика - тот же счётчик по минутам, только сумма до минуты считается не перебором минут, а за логарифм.

Механизм: дерево по значениям и спуск

Ячейка i дерева Фенвика отвечает за отрезок значений длиной i & −i - младший единичный бит номера, приём из раздела 19. Добавление игрока с очками x поднимается по ячейкам x + 1, прибавляя младший бит; сумма «не больше x» спускается, вычитая его. Обе операции проходят log₂ 1001 ≈ 10 ячеек. Смена очков игрока - два добавления: −1 к старым очкам и +1 к новым.

Обратный вопрос - «чьи очки k-е снизу» - решает спуск по дереву Фенвика. Размер дерева берут степенью двойки, и ответ собирают прыжками 1024, 512, …, 1: прыжок делают, если в отрезке, который он перепрыгивает, меньше k игроков, - и вычитают их из k. Каждый прыжок проверяет одну ячейку, всего проверок log₂ 1024 + 1 = 11. k-й сверху - это (n − k + 1)-й снизу.

Место при равных очках - вопрос спецификации, не алгоритма. Формула «1 + число игроков строго выше» даёт спортивный счёт: 1, 2, 2, 4. Порядковый номер в списке считается тем же деревом. «Плотный» счёт 1, 2, 2, 3 - нет: ему нужно число РАЗНЫХ значений очков выше игрока, и для этого рядом держат второе дерево, где у каждого занятого значения единица. Ставят её, когда число игроков с этими очками стало 1, и снимают, когда оно упало до 0, - это число даёт первое дерево. Это разные ответы, и выбрать надо до кода.

Правило

Место в рейтинге - префиксная сумма по ОСИ ОЧКОВ, а не по игрокам: дерево Фенвика по значениям считает его и обновляется за log. «Кто в k-й строке таблицы» - спуск по тому же дереву прыжками степеней двойки. Что такое место при равных очках, решает спецификация.

Разбор: сто партий, четыреста игроков

Игроки со случайными очками, сто партий: после каждой один игрок меняет очки на ±30 и смотрит место. Сравниваем дерево с перебором.

import random

random.seed(17)
MAKS = 1000                        # очки от 0 до 1000
igroki = []
for i in range(400):
    igroki.append(random.randint(0, MAKS))
fenvik = [0] * (MAKS + 2)          # индексы 1..MAKS+1: очки + 1
rabota = [0, 0]                    # [перебором, деревом Фенвика]

def dobavit(ochki, d):
    # в дереве Фенвика (раздел 8) число игроков с такими очками += d
    i = ochki + 1
    while i <= MAKS + 1:
        rabota[1] = rabota[1] + 1
        fenvik[i] = fenvik[i] + d
        i = i + (i & -i)

def ne_bolshe(ochki):
    # сколько игроков набрали очков не больше ochki
    i = ochki + 1
    s = 0
    while i > 0:
        rabota[1] = rabota[1] + 1
        s = s + fenvik[i]
        i = i - (i & -i)
    return s

def mesto_derevom(ochki):
    # место = 1 + число игроков СТРОГО выше
    return 1 + len(igroki) - ne_bolshe(ochki)

def mesto_pereborom(ochki):
    vyshe = 0
    for x in igroki:
        rabota[0] = rabota[0] + 1
        if x > ochki:
            vyshe = vyshe + 1
    return 1 + vyshe

for x in igroki:
    dobavit(x, 1)
rabota[1] = 0
sovpalo = True
for partiya in range(100):
    # после партии игрок меняет очки и смотрит своё место
    kto = random.randint(0, len(igroki) - 1)
    novye = min(MAKS, max(0, igroki[kto] + random.randint(-30, 30)))
    dobavit(igroki[kto], -1)
    dobavit(novye, 1)
    igroki[kto] = novye
    if mesto_derevom(novye) != mesto_pereborom(novye):
        sovpalo = False
print("места совпали:", sovpalo, "| партий: 100, игроков:", len(igroki))
print("перебором:", rabota[0], "сравнений | деревом:", rabota[1],
      "шагов")

места совпали: True | партий: 100, игроков: 400
перебором: 40000 сравнений | деревом: 1478 шагов

Места совпали во всех ста партиях. Перебор платит числом игроков за каждый вопрос - 400 на партию. Дерево платит логарифмом от числа ЗНАЧЕНИЙ очков - около 10 ячеек на каждое из двух обновлений и на запрос, около 15 шагов на партию с учётом коротких путей. На 10 000 игроков перебор стоит 10 000 на партию, а дерево - те же полтора десятка: оно вообще не зависит от числа игроков. Граница правила: дерево по значениям требует небольшого диапазона очков. Если очки - дробные или до миллиарда, значения сначала сжимают: сортируют все встречающиеся и заменяют номером по порядку, а дерево строят по номерам. Это работает, когда все значения известны заранее, - например, когда сервер обрабатывает журнал партий целиком. Если новые значения появляются на ходу, вместо дерева по номерам берут сбалансированное дерево поиска с размерами поддеревьев из раздела 8.

Разбор: кто на пятом месте и что такое третье

Десять игроков, у некоторых равные очки. Считаем места спортивным счётом и спуском находим очки игрока на 1-м, 3-м и 5-м месте списка.

MAKS = 1000
RAZMER = 1024                      # степень двойки не меньше MAKS + 1
fenvik = [0] * (RAZMER + 1)
ochki = [900, 850, 850, 800, 700, 700, 700, 650, 600, 420]

def dobavit(x, d):
    i = x + 1
    while i <= RAZMER:
        fenvik[i] = fenvik[i] + d
        i = i + (i & -i)

def ne_bolshe(x):
    i = x + 1
    s = 0
    while i > 0:
        s = s + fenvik[i]
        i = i - (i & -i)
    return s

def k_ya_snizu(k):
    # спуск по дереву: прыжки 512, 256, ..., 1 - каждый, если слева от
    # конца прыжка меньше k игроков. Ответ - очки k-го снизу, за log
    poz = 0
    shag = RAZMER
    while shag > 0:
        if poz + shag <= RAZMER and fenvik[poz + shag] < k:
            poz = poz + shag
            k = k - fenvik[poz]
        shag = shag // 2
    return poz                      # индекс poz + 1 - это очки poz

for x in ochki:
    dobavit(x, 1)
n = len(ochki)
mesta = []
for x in ochki:
    mesta.append(1 + n - ne_bolshe(x))
print("очки: ", ochki)
print("места:", mesta)
for k in [1, 3, 5]:
    print("на", k, "месте сверху очков:", k_ya_snizu(n - k + 1))

очки:  [900, 850, 850, 800, 700, 700, 700, 650, 600, 420]
места: [1, 2, 2, 4, 5, 5, 5, 8, 9, 10]
на 1 месте сверху очков: 900
на 3 месте сверху очков: 850
на 5 месте сверху очков: 700

Спортивный счёт дал 1, 2, 2, 4: двое с 850 делят второе место, третьего места нет. Спуск на вопрос «третий сверху» ответил 850 - это третий ИГРОК в списке, и он стоит на втором МЕСТЕ. Оба ответа верны, и именно поэтому спецификация обязана сказать, что показывать: «третье место - никого» или «третья строка таблицы - игрок с 850». Спуск сделал по одиннадцать проверок на каждый вопрос - без сортировки и без прохода по игрокам. Граница правила: спуск находит ОЧКИ k-го, а не самого игрока. Чтобы назвать игрока, рядом держат словарь «очки → игроки с этими очками».

Что ломается без этого

Сортировка после каждой партии. На тестовом сервере с сотней игроков всё мгновенно, на живом с десятью тысячами - n log n на каждый вопрос, и таблица лидеров отстаёт тем сильнее, чем больше игроков.

Дерево по игрокам. Построили Фенвика по номерам игроков - и он отвечает на «сумма очков игроков с 1 по 100», которая никому не нужна.

Место без договорённости. Два игрока с равными очками видят «2-е место» и «3-е место» - и пишут в поддержку, кто из них настоящий второй.

Зачем это в работе

Таблицы лидеров, перцентили времени ответа («сколько запросов быстрее 200 мс»), медиана в потоке данных при известном диапазоне значений, позиция товара в рейтинге продаж - везде, где нужен ранг при меняющихся данных, дерево по значениям отвечает за логарифм. А сжатие значений делает приём годным и для дробных, и для огромных чисел.

Теперь сам

1. Очки: [500, 500, 500, 300]. Какие места у игроков в спортивном счёте? Кто третий в списке?
2. Очки - от 0 до 10⁹, игроков 10⁵. Как построить дерево Фенвика, чтобы оно поместилось в память?
3. Сколько ячеек проверит спуск из программы урока, если размер дерева 4096?