【競プロ】3進数FenwickTreeを作りたかった話

はじめに

この記事は新歓ブログリレー2026 24 日目の記事です

できたもの

これを見てください：https://atcoder.jp/contests/practice2/submissions/74172940
別にこれから解説するので、見なくても構いません (← おい)

導入

最近、平衡三進法に関する問題を解いて、三進数について興味をもって調べていたところ、3値論理回路を作ってみたという興味深い記事を見つけました。
どうやら、「3進数コンピューター」という概念があるようです。私も、2億年後ぐらいに来たる3進数コンピューターのブームに乗るため、いち競プロerとして、少しながら考察してみることにしました。

して、今回扱うのは FenwickTree (別名： BIT (Binary Indexed Tree)) です。

データ構造の中には、ビット演算が高速にできることを前提としてデータ構造があります。
例えば、FenwickTreeやセグ木など、これらの実装にはビット演算が効果的に用いられています。具体的には「ある数を割ることができる最大の $2$ の累乗数を求める」だとか「ある数を2で割る」だとか「ある数が偶数ならそのまま、奇数なら1を引く」とか、これらの操作はどれも定数回のビット演算で求めることができます。このような操作が高速に行えるからこそ、FenwickTreeやセグ木は定数倍が軽いデータ構造として重宝される訳です。

ちなみに、ビット演算がサポートされてない言語もあるみたいです。~~TeXって言うんですけど...~~

さてさて、セグ木やFenwickTreeがビット演算と相性がいい、と述べてきましたが、そもそもビット演算とは、2進数表記された数に対しての原始的な操作です。つまり、この世界のCPUは2進数で動いているからこそ、ビット演算は使える訳です。では、もしこの世界のコンピューターが3進数を採用したら...？

そこにはビット演算(bit) ではなくトリット演算(trit) が使われることでしょう。

ということで、3進数ベースの世界と相性が良さそうな、FenwickTreeの類似を考えてみよう！　というのがこのブログの目的です。

以下、説明中での配列は1-indexedであるとします。

FenwickTreeの仕組み

FenwickTree 自体の説明は面倒くさいので、詳しく知りたい人は適当にググってください。

----------2026-03-09-221418

スプレッドシートで5分で作った図です。

FenwickTree は、ある配列に対する Prefix Sum を高速に計算できます。仕組みとしては、2の累乗のサイズの連続部分列の和 を事前に計算しておくことで、クエリあたり O(log N) 回の足し算で求める和を計算します。

例えば、配列を A = [4, 6, 3, 4, 1, 5, 0, 2] としたとき、上図のようなテーブルを作ります。各白いセルは、その範囲に対応する元の配列の和を持ちます。例えば、上から2段目の左のセル7は、A[1]+A[2]+A[3]+A[4]=4+6+3+4=17となります。

さて、この前計算から、例えば以下のように Prefx Sum を取ることができます。

----------2026-03-09-222830

A[1]+...+A[7] = (A[1]+...+A[4]) + (A[5]+A[6]) + (A[7]) = 17 + 6 + 0 = 23
オレンジ色のノードを取ることで、区間和を取ることができます。一般的にこのようなことができる理由に関しては各自調べてください。

さて、注目するべきは各ノードの区間の長さです。今回使ったノードの長さは,4,2,1 ですね。一般的に FenwickTree では、各ノードの長さが2の累乗になります。つまり Prefix Sum を求める時に、前の部分から貪欲に大きな2の累乗の長さのノードを取っていくことで効率よく計算しているのです。

そもそも、2の累乗の長さのノードを貪欲に取っていってその値を表現できるのは、2進数の性質より、

任意の整数は、2のべき乗数を「足す、足さない」を選ぶことで表現できる

という事実が成り立つからです。

平衡3進数

普通の3進数を用いたとき、任意の非負整数 $n$ は、適当な係数 $c_{i} \in {0, 1, 2}$ を用いて、

n = i = 0 \sum \infty c_{i} \cdot 3^{i}

という形で表せます。(ただし、十分大きい $n$ に対して常に $c_{n} = 0$ であるとします。)

これが一般的な3進数の表現方法です。
しかし、係数に負の値を許すことで、次のような表現方法もあります。
任意の整数 $n$ は、適当な係数 $c_{i} \in {- 1, 0, 1}$ を用いて、

n = i = 0 \sum \infty c_{i} \cdot 3^{i}

という形で表せます。(ただし、十分大きい $n$ に対して常に $c_{n} = 0$ であるとします。)
これが平衡3進法です。具体例を見てみましょう。例えば、

7 = 1 \times 3^{2} + (- 1) \times 3^{1} + 1 \times 3^{0}

- 5 = (- 1) \times 3^{2} + 1 \times 3^{1} + 1 \times 3^{0}

3 = 0 \times 3^{2} + 1 \times 3^{1} + 0 \times 3^{0}

のような感じです。定性的に説明するならば、

任意の整数は、3のべき乗数を「足す、引く、何もしない」を選ぶことで表現できる

ということです。なんだか似た話が前の節でありましたね...このアイデアこそが、3進数FenwickTreeの本質です。

原案

----------2026-03-16-225214

図のような部分の和を計算することを考えます。言語的に説明するなら、

1段目が幅1のノードを分割する
2段目が幅3のノードに分割する
3段目が幅9のノードに分割する

...
とした後、「あるノードが上のノードの中心と同じ位置にある」ときにそのブロックを黒く塗り(使わない)、そうでないときそのノードのカバーする範囲の和を取る

ということをします。下の動画を見たほうが分かりやすいかもしれません。

0:00

さて、重要な事実として、この表は今は2次元的に書いていますが、1次元の配列に落とし込むことができます。例えば、元配列を A、表をBとしたときに、

B[1] = A[1]
B[2] = A[1] + A[2] + A[3]
B[3] = A[3]
B[4] = A[4]
B[5] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] + A[9]
B[6] = A[6]
B[7] = A[7]
B[8] = A[7] + A[8] + A[9]
B[9] = A[9]

とすることで、できます。ちょうど各ノードの中心の真下は空いているので、それを落として来た感じと言ったらいいでしょうか。
あるいは、あるB[i]の値がどうなるかは、以下のように表現できます。

まずi-1を三進数表記します
その下の桁から連続する1を*に置き換えます
↑によって得られた*を独立に0 1 2に置き換えた時に得られる数を列挙します
↑によって得られた数の列挙に対して、それぞれに1を加算します

例えば、B[23]だったら、23-1=0t211であるので、0t200, 0t201, 0t202, 0t210, 0t211, 0t212, 0t220, 0t221, 0t222 = 18, 19, 20, 21, 22, 23, 24, 25, 26、これに+1して、19, 20, 21, 22, 23, 24, 25, 26, 27である。よって、

B[23] = A[19] + A[20] + A[21] + A[22] + A[23] + A[24] + A[25] + A[26] + A[27]

であると分かります。(実際にこうやって求めることはありませんが...)

そして、先頭からの和を求めるときは下図のように、最上位のノードから足して引いてをすることでできます。図を見てください。

----------2026-03-17-001154

この具体例では、赤色のノードを足し、青色のノードを引くことで、A[1]~A[22] までの和を表しています。一般にこれは可能です。これができるのは先に述べた平衡三進数による表現が存在することと同値です。具体的には、22を平衡三進数で表すと+-++となるのですが、これはちょうど上図における、上から赤青赤赤と取っている事実と対応します。

実装

初期化

初期化はinplaceにO(N)で行う事ができます。具体的には、和を取るノードの左右から値を集めてくることで可能です。

また、上の説明では配列の長さを3の累乗で固定していますが、実際は $\frac{3 ^{k} - 1}{2}$ の形にしています。この形は、k 桁の平衡三進数の上限値の形です。この値を超えるかどうかが、一番上のノードが切り替わるタイミングなので、これで実装したほうが見栄えがいい...かも？

struct TIT{
    vector<T> array;
    size_t sz;

    void init(It first, It last){
        // 冒頭に0を挿入したうえで初期化
        array.clear();
        array.push_back(0);
        array.insert(array.end(), first, last); // 元の配列を代入、inplaceにできるってだけでデータ構造なのでしないです。

        // サイズを (3^k-1)/2 型 にする。3の累乗でもいいけど平衡三進数的にはこれが自然。
        int tmp = 1;
        while (tmp < (int)array.size()) {
            tmp = 3*tmp+1;
        }
        array.resize(tmp+1, 0); // 1-indexed なので +1 する
        sz = array.size() - 1;

        // テーブルの構築
        int pos = 2;
        int p = 1;
        while (pos < (int)array.size()) {
            for (int i = pos; i <= (int)sz; i+=3*p) {
                array[i] += array[i - p];
                array[i] += array[i + p];
            }
            pos = 3 * pos - 1;
            p *= 3;
        }
    }

    }
};

参考
----------2026-03-17-004056

値の集計

値の取得は、平衡三進数を下の桁から決定することで、どのノードを足し引きするかを計算していきます。この処理を行う上で、平衡三進法上でのビット演算が使えたら楽だな～になります。

    T sum(int ind){
        T res = 0;
        int p = 1;
        while (ind > 0){
            if (ind % 3 == 1){
                res += array[ind*p - (p-1)/2];
                ind -= 1;
            } else if (ind % 3 == 2){
                ind += 1;
                res -= array[ind*p - (p-1)/2];
            }
            ind /= 3;
            p *= 3;
        }
        return res;
    }

値の加算

セグ木みたいに、上のノードに上がり続けることを繰り返せばよいです。

    void add(int ind, T x){
        int p = 1;
        while (ind*p <= sz){
            if (ind % 3 != 2){
                array[ind*p - (p-1)/2] += x;
            }
            ind = (ind-1)/3+1;
            p *= 3;
        }
    }

最終的なコード

// @brief TernaryIndexedTree
template <typename T>
struct TIT {
    vector<T> array;
    size_t sz;
    TIT(initializer_list<T> init_list){
        init(init_list.begin(), init_list.end());
    }

    TIT(const vector<T>& init_vec){
        init(init_vec.begin(), init_vec.end());
    }

private:
    template <class It>
    void init(It first, It last){
        // 冒頭に0を挿入したうえで初期化
        array.clear();
        array.push_back(0);
        array.insert(array.end(), first, last); // 元の配列を代入

        // サイズを (3^k-1)/2 型 にする。3の累乗でもいいけど平衡三進数的にはこれが自然。
        int tmp = 1;
        while (tmp < (int)array.size()) {
            tmp = 3*tmp+1;
        }
        array.resize(tmp+1, 0); // 1-indexed なので +1 する
        sz = array.size() - 1;

        // テーブルの構築
        int pos = 2;
        int p = 1;
        while (pos < (int)array.size()) {
            for (int i = pos; i <= (int)sz; i+=3*p) {
                array[i] += array[i - p];
                array[i] += array[i + p];
            }
            pos = 3 * pos - 1;
            p *= 3;
        }
    }

public:

    T cum(int ind){
        T res = 0;
        int p = 1;
        while (ind > 0){
            if (ind % 3 == 1){
                res += array[ind*p - (p-1)/2];
                ind -= 1;
            } else if (ind % 3 == 2){
                ind += 1;
                res -= array[ind*p - (p-1)/2];
            }
            ind /= 3;
            p *= 3;
        }
        return res;
    }

    T get(int ind){
        return cum(ind) - cum(ind-1);
    }

    void add(int ind, T x){
        int p = 1;
        while (ind*p <= sz){
            if (ind % 3 != 2){
                array[ind*p - (p-1)/2] += x;
            }
            ind = (ind-1)/3+1;
            p *= 3;
        }
    }

    void write(int ind, T x){
        add(ind, x - get(ind));
    }

    size_t size(){
        return sz;
    }


};

varify : https://atcoder.jp/contests/practice2/submissions/74172940
Github : https://github.com/n-and-n3/KyoproLibrary/blob/main/cpp/TernaryIndexedTree.cpp

インターフェイスは FeneickTree(BIT) と同じです。できることも同じです。
さて、このデータ構造には BIT を真似て TIT (TernaryIndexedTree) という名前を付けてあげました。皆さん名前だけでも覚えて帰ってください。

結論

比較のために、BITを作って提出してみました (206ms)。TITが(255 ms) なので、やはり定数倍で負けてますね...。

いかがでしたか？

平衡三進数など見ずとも、セグ木が2分木ではなく3分木だったらどうしよう？とか考えたことがあるのではないでしょうか。この記事は、そんな妄想を考察した結果できたものです。
今はまだ2進数コンピューターが覇権を握っていますが、いずれ来る3進数コンピューターの世界では、TITが活躍することを願っています。

おまけ

せっかくなら、trit 演算を使って実装してみたくないですか？
ということで、trit 演算が行える整数型 trint を実装して(Geminiが)、TITの実装を一部書き換えて見ました。

長いので折りたたみ


class trint {
private:
    int val;
    // 3^20 = 3,486,784,401. 
    // 平衡三進数20桁の最大値は (3^20 - 1) / 2 = 1,743,392,200.
    // これは 32bit signed int (最大 2,147,483,647) に安全に収まる。
    static const int TRIT_WIDTH = 20; 

    // int -> 平衡三進数の配列(下位桁から順に格納)
    std::array<int, TRIT_WIDTH> to_trits() const {
        std::array<int, TRIT_WIDTH> trits = {0};
        long long n = val;
        for (int i = 0; i < TRIT_WIDTH; ++i) {
            int rem = n % 3;
            if (rem < 0) rem += 3;
            
            if (rem == 2) {
                trits[i] = -1;
                n = (n + 1) / 3;
            } else {
                trits[i] = rem;
                n = (n - rem) / 3;
            }
        }
        return trits;
    }

    // 平衡三進数の配列 -> int
    static int from_trits(const std::array<int, TRIT_WIDTH>& trits) {
        long long res = 0;
        long long p = 1;
        for (int i = 0; i < TRIT_WIDTH; ++i) {
            res += trits[i] * p;
            p *= 3;
        }
        return static_cast<int>(res);
    }

public:
    // コンストラクタ
    trint(int v = 0) : val(v) {}
    
    // 文字列からの初期化
    trint(const std::string& s) {
        std::array<int, TRIT_WIDTH> trits = {0};
        int len = s.length();
        for (int i = 0; i < len && i < TRIT_WIDTH; ++i) {
            char c = s[len - 1 - i]; // 下の桁(右側)からパース
            if (c == '+') trits[i] = 1;
            else if (c == '-') trits[i] = -1;
            else trits[i] = 0;
        }
        val = from_trits(trits);
    }

    // 暗黙のint型変換
    operator int() const { return val; }

    // --- トリット演算 ---

    trint operator-() const { return trint(-val); }

    // 単項~: 巡回シフト (+ -> -, 0 -> +, - -> 0)
    trint operator~() const {
        auto trits = to_trits();
        for (int i = 0; i < TRIT_WIDTH; ++i) {
            if (trits[i] == 1) trits[i] = -1;
            else if (trits[i] == 0) trits[i] = 1;
            else if (trits[i] == -1) trits[i] = 0;
        }
        return trint(from_trits(trits));
    }

    // 二項&: Trit-wise MIN
    trint operator&(const trint& other) const {
        auto t1 = to_trits();
        auto t2 = other.to_trits();
        std::array<int, TRIT_WIDTH> res;
        for (int i = 0; i < TRIT_WIDTH; ++i) {
            res[i] = std::min(t1[i], t2[i]);
        }
        return trint(from_trits(res));
    }

    // 二項|: Trit-wise MAX
    trint operator|(const trint& other) const {
        auto t1 = to_trits();
        auto t2 = other.to_trits();
        std::array<int, TRIT_WIDTH> res;
        for (int i = 0; i < TRIT_WIDTH; ++i) {
            res[i] = std::max(t1[i], t2[i]);
        }
        return trint(from_trits(res));
    }

    // 二項^: Trit-wise 積
    trint operator^(const trint& other) const {
        auto t1 = to_trits();
        auto t2 = other.to_trits();
        std::array<int, TRIT_WIDTH> res;
        for (int i = 0; i < TRIT_WIDTH; ++i) {
            res[i] = t1[i] * t2[i];
        }
        return trint(from_trits(res));
    }

    // シフト演算子
    trint operator<<(int shift) const {
        auto trits = to_trits();
        std::array<int, TRIT_WIDTH> res = {0};
        for (int i = 0; i < TRIT_WIDTH - shift; ++i) {
            res[i + shift] = trits[i];
        }
        return trint(from_trits(res));
    }

    trint operator>>(int shift) const {
        auto trits = to_trits();
        std::array<int, TRIT_WIDTH> res = {0};
        for (int i = shift; i < TRIT_WIDTH; ++i) {
            res[i - shift] = trits[i];
        }
        return trint(from_trits(res));
    }

    // --- 複合代入演算子 ---
    trint& operator&=(const trint& rhs) { *this = *this & rhs; return *this; }
    trint& operator|=(const trint& rhs) { *this = *this | rhs; return *this; }
    trint& operator^=(const trint& rhs) { *this = *this ^ rhs; return *this; }
    
    trint& operator+=(const trint& rhs) { val += rhs.val; return *this; }
    trint& operator-=(const trint& rhs) { val -= rhs.val; return *this; }
    trint& operator*=(const trint& rhs) { val *= rhs.val; return *this; }
    trint& operator/=(const trint& rhs) { val /= rhs.val; return *this; }
    trint& operator%=(const trint& rhs) { val %= rhs.val; return *this; }

    trint& operator<<=(int shift) { *this = *this << shift; return *this; }
    trint& operator>>=(int shift) { *this = *this >> shift; return *this; }

    // --- インクリメント・デクリメント ---
    trint& operator++() { ++val; return *this; }
    trint operator++(int) { trint temp = *this; ++val; return temp; }
    trint& operator--() { --val; return *this; }
    trint operator--(int) { trint temp = *this; --val; return temp; }

    // --- 表示用 ---
    std::string to_string() const {
        if (val == 0) return "0";
        auto trits = to_trits();
        std::string s = "";
        bool leading = true;
        for (int i = TRIT_WIDTH - 1; i >= 0; --i) {
            if (trits[i] != 0) leading = false;
            if (!leading) {
                if (trits[i] == 1) s += "+";
                else if (trits[i] == -1) s += "-";
                else s += "0";
            }
        }
        return s;
    }

    // friend関数としてストリーム演算子を定義
    friend std::istream& operator>>(std::istream& is, trint& t) {
        std::string s;
        is >> s;
        // 入力文字列が "+-0" のみで構成されているかチェック
        if (s.find_first_not_of("+-0") == std::string::npos) {
            t = trint(s); // 平衡三進数文字列としてパース
        } else {
            t = trint(std::stoi(s)); // 10進数整数としてパース
        }
        return is;
    }
};

// 算術演算子 (非メンバ関数)
trint operator+(trint lhs, const trint& rhs) { lhs += rhs; return lhs; }
trint operator-(trint lhs, const trint& rhs) { lhs -= rhs; return lhs; }
trint operator*(trint lhs, const trint& rhs) { lhs *= rhs; return lhs; }
trint operator/(trint lhs, const trint& rhs) { lhs /= rhs; return lhs; }
trint operator%(trint lhs, const trint& rhs) { lhs %= rhs; return lhs; }

// 出力ストリーム
std::ostream& operator<<(std::ostream& os, const trint& t) {
    os << t.to_string();
    return os;
}
// ==========================================================================

#include <vector>
#include <iostream>

// @brief 真のTernaryIndexedTree (Powered by trint)
template <typename T>
struct TIT {
    vector<T> array;
    size_t sz;
    TIT(initializer_list<T> init_list){
        init(init_list.begin(), init_list.end());
    }

    TIT(const vector<T>& init_vec){
        init(init_vec.begin(), init_vec.end());
    }

private:
    template <class It>
    void init(It first, It last){
        // 冒頭に0を挿入したうえで初期化
        array.clear();
        array.push_back(0);
        array.insert(array.end(), first, last); // 元の配列を代入

        // サイズを (3^k-1)/2 型 にする。3の累乗でもいいけど、平衡三進数的にはこれが自然。
        trint tmp = 1;
        while (tmp < (trint)array.size() - trint(1)) {
            tmp = (tmp << 1) + trint(1);
        }
        array.resize(tmp+trint(1), 0); // 1-indexed なので +1 する
        sz = array.size() - 1;

        // テーブルの構築
        trint pos = 2;
        trint p = 1;
        while (pos < (trint)array.size()) {
            for (trint i = pos; i <= (trint)sz; i+=trint(3)*p) {
                array[i] += array[i - p];
                array[i] += array[i + p];
            }
            pos = (pos << 1) - trint(1);
            p <<= 1;
        }
    }

public:

    T cum(trint ind){
        T res = 0;
        trint pos = 0;
        for (int i = 0; i < 60 && ind > 0; ++i) { // 60は適当な上限値
            if ((ind ^ trint(1)) == 1){
                res += array[(ind<<i) - pos];
                ind -= 1;
            } else if ((ind ^ trint(1)) == -1){
                ind += 1;
                res -= array[(ind<<i) - pos];
            }
            ind >>= 1;
            pos = (pos << 1) + trint(1);
        }
        return res;
    }

    T get(trint ind){
        return cum(ind) - cum(ind-trint(1));
    }

    void add(trint ind, T x){
        trint pos = 0;
        for (int i=0; (ind<<i) <= sz; i++){
            if ((ind ^ trint(1)) != -1){
                array[(ind<<i) - pos] += x;
            }
            ind = (ind-trint(1))/trint(3)+trint(1);  // ここはうまくtrit演算を使えなかった
            pos = (pos << 1) + trint(1);
        }
    }

    void write(trint ind, T x){
        add(ind, x - get(ind));
    }

    size_t size(){
        return sz;
    }


};

提出 (4616 ms)：https://atcoder.jp/contests/practice2/submissions/74173913
平衡三進数を無理やりシミュレーションしてるため激重です。

おまけ2

ただの独り言兼メモです。読まなくて構いません。

そういえばこのブログのタイトルは「3進数FenwickTreeを作りたかった話」です。

あれ作ってるじゃん、完成じゃないの？

そうなんですが、これただの BIT の劣化品ですよね...
実は、設計をする前は、BITとの差別化ができるような要件定義をしていました。ですが設計するにつれてそのような実装が難しいことに気づき、泣く泣く諦めたというわけです。

その要件とは、「dequeのような両端push可能なFenwickTreeを作成する」です。

あまり言及されている印象がありませんが、例えばFenwickTreeをvectorで実装したとき、配列の末尾へのpushが可能です。参考
そこで、平衡三進数をindexに使えば、平衡三進数の値域は0を中心に対称性を持つし、両端に対して対称的な push 可能な構造になるのではないか？とか妄想してたわけです。

ですが、データをどうにも乗せても、pushするときに簡単にできない！ってので諦めてしまいました。
そもそも「うまくpushできる」の定義も曖昧なのでちゃんと説明すると、

1回の計算量が最悪 $O (l o g N)$ である。(償却ではダメ)
vector, deque のメモリ再確保はそもそも償却計算量であるが、そこは無視する。

として検討していました。つまり vector, deque が償却計算量を要求しても、FenwickTree のアルゴリズムの方は償却ではないように働くようにしたいな～という感じで作っていました。

そもそも償却を許せば、「dequeをstack2本で再現するテク」とFenwickTreeで実装できますしね...

結果、どうにもコネコネしても負番indexで左右対称にするいい実装は思いつかず、両端pushを行う計画は諦めました。そもそも先に紹介した図を見れば分かる通り、余分に長い部分のノードにはみ出たりしているので、まあ最悪計算量がどうしても悪化してしまうのはしょうがないなぁと言った感じですかね...

参考画像：そもそも index を負番まで拡張しようとか考えてました。データのもたせ方に並進対称性が無いので、dequeみたいに単純にindexをずらすことができないので仕方無いですね...
132736

参考画像：値の集計アルゴリズムのメモです。セグ木みたいに非再帰でいい感じにコネコネした痕跡が見受けられます。

一応↑画像の方針で実装したものもあるので、ここで供養します。verifyはしてないので参考までに。
githubのリンク：https://github.com/n-and-n3/KyoproLibrary/blob/main/trash/TernaryIndexedTree_botsu.cpp

長いので折りたたみ

// 座標を負の方向に伸ばせるvector、デキューのインデックスがズレていかないもの、と解釈できる
template <typename T>
struct devector{
    deque<T> devec;
    int offset;

    devector(int start,int goal, T init_val) : devec(goal-start+1,init_val), offset(start){}

    T& operator[] (int x){
        return devec[x-offset];
    }

    int start(){
        return offset;
    }

    int goal(){
        return devec.size() + offset - 1;
    }

    void push_back(const T& val){
        devec.push_back(val);
    }

    void push_front(const T& val){
        devec.push_front(val);
        offset -= 1;
    }

    void pop_back(){
        assert(!devec.empty());
        devec.pop_back();
    }

    void pop_front(){
        assert(!devec.empty());
        devec.pop_front();
        offset += 1;
    }

};
    
// @brief TernaryIndexedTree
struct TIT {
    devector<ll> table;
    int _start;
    int _goal;
    int count;

    TIT(devector<int> array) : _start(array.start()), _goal(array.goal()){
        int N = 1;
        chmax(N, -array.start());
        chmax(N, array.goal());
        int tmp = 1;
        count = 1;
        while (tmp < N){
            tmp = 3*tmp+1;
            count += 1;
        }
        N = tmp;

        while (array.goal() < N){
            array.push_back(0);
        }

        while (-N < array.start()){
            array.push_front(0);
        }

        table.assing(-N,N,0);

        for (int i=0;i<=count;i++){
            if (i == 0){
                for(int j=-N;j<=N;j++){
                    table[j] = array[j];
                }
            } else {
                auto tmp = (trint(1)<<(i-1));
                for (int j=((trint(-N)>>i)<<i);j<=((trint(N)<<i)>>i);j+=(trint(1)<<i)){
                    table[j] = table[j-tmp] + table[j] + table[j+tmp];
                }
            }
        }
    }

    int prod(trint l, trint r){
        int ans1 = 0;
        int ans2 = 0;

        trint t = 1;

        for (int i = 0; (r!=l && r != trint(0) && l !=  trint(0)) || i<count;i++){
            if (l[i] == 0){
                l=l-t;
                ans1 = ans1 + (-table[l]);
            } else if (l[i] == 1){
                ans1 = ans1 + table[l];
                l=l+t;
            }
            l[i] = 0;

            if (r[i] == 0){
                r=r+t;
                ans2 = (-table[r]) + ans2;
            } else if (r[i] == -1){
                ans2 = table[r] + ans2;
                r=r-t;
            }
            r[i] = 0;
            t = t * trint(3);
        }

        return ans1 + table[l] + ans2;
    }

    int get(trint ind){
        return prod(ind,ind);
    }

    void write(trint ind, int x){
        int pre = get(ind);
        int s = 0;
        trint c = ind;
        while(c[0] == 0){
            c = c >> 1;
            s++;
        }
        for (int i=s;i<=count;i++){
            table[(ind>>i)<<i] += x - pre;
        }
    }

    int start(){
        return _start;
    }
    
    int goal(){
        return _goal;
    }


    
};

おわりに

わざわざ私の妄言まで読んできただきありがとうございます。
多分もっと良い実装とかがあると思いますが、私には思いつきませんでした。ですが、自分でデータ構造を考えてみるということができたのは楽しかったです。

それでは、皆様もデータ構造で良き競プロライフを～

明日の記事は @mirin さんです。