AtCoder ABC157 E - Simple String Queries を ORのセグメント木で解く

https://atcoder.jp/contests/abc157/tasks/abc157_e

TallfallさんのSubmitをみて、なるほどと思ったのでdump。これは頭いい..
https://atcoder.jp/contests/abc157/submissions/10434154

# 概要
- N文字の文字列sが与えられる
- 以下のq個のクエリに応えよ
- type1: sのi文字目をaに書き換える
- type2: l文字目からr文字目に含まれる文字の種類を述べよ

# 考えたこと
single update, range queryなので、以下のような典型アプローチが考えられる
- 1つのセグ木(sum)で26文字分のcountをする, 26個のRSQに応えるセグ木を持つ, bittree
自分は26個のセグ木を生やしたけどTLEが取れなかった。(これは自作ライブラリが多分に悪い)

# 標題のアプローチ
各文字を$aをx=0, zをx=25$として`1 << x`のビットシフトした値として扱う。(つまり、a=1, b=2, c=4...)これをデータとして持つセグメント木を 論理演算`or`で作る。つまり、以下の図のような感じ。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/f50075da-491b-4f72-bd26-73ff290fa843.png" width=50%>

各文字はデータとして入れる際、上記のようにビットシフトした数値として入れる。ノードは下位ノードの論理ORを取って自ノードの値として持つ。カウントしたいのは、文字の種類であるから、立っている1の数をカウント$(つまりpopcount)$すればよい。

実装はとてもシンプルで通常のRMQ, RSQで演算としてORを乗せれば終わり。updateの際に`c`と渡したいか、`4`と渡したいかはどちらでも良いか、計算済みの値を渡した方が、ライブラリの改変量は少ないだろう。

入力は1originのindexであることと、セグ木のqueryは$[l, r)$に注意しよう。

# よくわかっていないこと
PyPyとPythonでほぼ実行速度もメモリも差が出ていない。のが説明できないのでちゃんと理解して使いたい。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/e0294d6d-f7bf-8ef0-fc5b-2e9fba81131b.png)


# コード

再帰使った練習用コードで通ったのでこれを記載。

```Python
class segmentTreeOR():
    initValue = 0
    dat = []
    lenTreeList = -1
    depthTreeList = 0
    lenOriginalList = -1
 
    def __init__(self):
        pass
 
    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenOriginalList = len(l)
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        self.dat = [self.initValue] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenTreeList - 1 + i] = l[i]
        self.build()
 
    def build(self):
        for i in range(self.lenTreeList - 2, -1, -1):
            self.dat[i] = self.dat[2 * i + 1] | self.dat[2 * i + 2]
 
    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        # print(" first nodeId: {0}".format(nodeId))
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            # print(" next nodeId: {0}".format(nodeId))
            self.dat[nodeId] = self.dat[nodeId * 2 + 1] | self.dat[nodeId * 2 + 2]
 
    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        if (r <= a or b <= l):
            return self.initValue
        if a <= l and r <= b:
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        return resLeft | resRight
 
    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)
 
# https://yottagin.com/?p=2808
def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
        count += int(i)
    return count
 
n = int(input())
s = input()
sl = list(s)
sl = list(map(lambda x: ord(x) - ord("a"), sl))
 
l = list(map(lambda x: 1 << x, sl))
 
st = segmentTreeOR()
st.load(l)
 
q = int(input())
for _ in range(q):
    ty, x, y = input().split()
    x = int(x)
    if ty == "1":
        nind = ord(y[0]) - ord("a") # 置き換えるindex
        st.setValue(x-1, 1 << nind)
    elif ty == "2":
        x = int(x) - 1
        y = int(y)
        res = 0
        cnt = st.query(x, y)
        print(count_ones_by_bin(cnt))
    else:
        print("error")
```

https://atcoder.jp/contests/abc157/submissions/10502012