Как построить обратный (инвертированный) индекс позиций каждого слова в боре?

Для чистого «слово → список позиций» обычно достаточно unordered_map<string, vector<int>>: вставка O(|word|) на хеш + amortized, запрос O(|word|). Бор выигрывает в двух случаях:

1. Префиксные запросы: «все позиции слов, начинающихся на pre» — в боре это поддерево, в map так не сделать без полного перебора ключей.
2. Много общих префиксов — бор экономит память, не дублируя префиксы (важно при огромных словарях).

Бор с обратным индексом:

struct InvIndex {
    struct Node { array<int,26> next; vector<int> positions; Node(){ next.fill(-1);} };
    vector<Node> t{1};
    void add(const string& w, int pos){
        int v=0;
        for(char ch:w){ int c=ch-'a';
            if(t[v].next[c]==-1){t[v].next[c]=t.size(); t.emplace_back();}
            v=t[v].next[c];
        }
        t[v].positions.push_back(pos);     // позиции вхождений именно этого слова
    }
    const vector<int>* query(const string& w){
        int v=0;
        for(char ch:w){ int c=ch-'a'; if(t[v].next[c]==-1) return nullptr; v=t[v].next[c]; }
        return t[v].positions.empty()? nullptr : &t[v].positions;
    }
};

Построение — O(суммарная длина слов), запрос — O(|word|). Позиции можно держать отсортированными (если добавляете по возрастанию pos — они уже отсортированы), что позволяет пересекать списки для запросов из нескольких слов.