Как-то так:
pastebin.com/K6Z8JqVT
То есть, идея в том, чтобы подписать узел на событие изменения состояния "маркера" при его добавлении в узел. При этом, узел распространяет события своему родителю (если он есть) вплоть до корневого. Каждый узел хранит компактный набор счетчиков состояний, связанных с его "маркерами" и "маркерами" дочерних узлов. Что-то еще более оптимизировать, на мой взгляд, смысла нет, т.к. TreeMap (O(nlog(n)) с ключом по состоянию -- это и так очень быстро.
Код, разумеется, не thread-safe.
