Поторопился с заголовком, пока только начинаю разрабатывать. Итак:

1. Дано: размеры W и H
2. Берем обычный массив размером W * H — здесь будут лежать значения. Если размер изменяется, то поступаем в точности как это происходит при увеличении хеш-таблиц — выделяем память и перекладываем. На самом деле тут 100500 вариаций, например, хранить не единым массивом, а чанками. 5 млн. ячеек — это мало, потянет даже ваш телефон
3. Все формулы хранятся тоже в этой таблице, при изменении зависимых ячеек идет пересчет
4. Пользователь имеет видимую часть x1, y1, x2, y2 — ее он отправляет на сервер, каждый раз меняя видимую часть на сервер уходят новые координаты
5. Каждый раз, когда на сервере изменяется ячейка происходит проверка затрагивает ли это какую-либо пользовательскую вьюху, тут есть тоже простор для оптимизаций, но вангую простым перебором по вьюхам проверить x1 <= x и x <= x2 будет гуд энаф
6. Если получили попадание, то оповещаем пользователя. Чтобы не гонять трафик, делаем отправку ленивую

Все. Вот теперь разрабатывать закончил. Заняло это аж минуты 3

Да, и чтобы самим не кодить таблицу берем, например, тарантул или даже редис, если нам сохранение целостности таблицы не критично.