Hash Segment Tree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct HashSegTree {
    static const ll P1 = 313, P2 = 1013, M1 = 1e9 + 7, M2 = 1e9 + 9;
    int n, sz;
    vector<ll> pw1, pw2, iv1, iv2;
    vector<pll> tree;

    ll mul(ll a, ll b, ll m) { return (__int128)a * b % m; }
    ll add(ll a, ll b, ll m) { return (a + b) % m; }
    ll power(ll b, ll e, ll m) {
        ll r = 1;
        while (e > 0) { if (e & 1) r = mul(r, b, m); b = mul(b, b, m); e >>= 1; }
        return r;
    }

    pll merge(pll a, pll b) { return {add(a.first, b.first, M1), add(a.second, b.second, M2)}; }

    HashSegTree(int _n = 0) : n(_n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        tree.assign(2 * sz, {0, 0});
        pw1.resize(2 * sz); pw2.resize(2 * sz);
        iv1.resize(2 * sz); iv2.resize(2 * sz);
        pw1[0] = pw2[0] = iv1[0] = iv2[0] = 1;
        ll i1 = power(P1, M1 - 2, M1), i2 = power(P2, M2 - 2, M2);
        for (int i = 1; i < 2 * sz; i++) {
            pw1[i] = mul(pw1[i-1], P1, M1);
            pw2[i] = mul(pw2[i-1], P2, M2);
            iv1[i] = mul(iv1[i-1], i1, M1);
            iv2[i] = mul(iv2[i-1], i2, M2);
        }
    }

    void build(const string &s, int idx, int lx, int rx) {
        if (lx > n) return;
        if (lx == rx) {
            ll v = s[lx - 1] - 'a' + 1;
            tree[idx] = {mul(v, pw1[idx], M1), mul(v, pw2[idx], M2)};
            return;
        }
        int mx = (lx + rx) / 2;
        build(s, 2*idx, lx, mx);
        build(s, 2*idx+1, mx+1, rx);
        tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
    }
    void build(const string &s) { build(s, 1, 1, sz); }

    void update(int pos, int val, int idx, int lx, int rx) {
        if (lx == rx) {
            tree[idx] = {mul(val, pw1[idx], M1), mul(val, pw2[idx], M2)};
            return;
        }
        int mx = (lx + rx) / 2;
        if (pos <= mx) update(pos, val, 2*idx, lx, mx);
        else update(pos, val, 2*idx+1, mx+1, rx);
        tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
    }
    void update(int pos, char c) { update(pos, c - 'a' + 1, 1, 1, sz); }
    void update(int pos, int val) { update(pos, val, 1, 1, sz); }

    pll query(int l, int r, int idx, int lx, int rx) {
        if (lx > r || rx < l) return {0, 0};
        if (lx >= l && rx <= r) return tree[idx];
        int mx = (lx + rx) / 2;
        return merge(query(l, r, 2*idx, lx, mx), query(l, r, 2*idx+1, mx+1, rx));
    }
    pll query(int l, int r) {
        auto [a, b] = query(l, r, 1, 1, sz);
        return {mul(a, iv1[l-1], M1), mul(b, iv2[l-1], M2)};
    }
};