3756. Concatenate Non-Zero Digits and Multiply by Sum II

class Solution {
    static final int MOD = 1_000_000_007;

    class Node {
        long val;
        int len;
        long sum;

        Node() {}

        Node(long v, int l, long s) {
            val = v;
            len = l;
            sum = s;
        }
    }

    Node[] tree;
    long[] pow10;
    char[] arr;

    public int[] sumAndMultiply(String s, int[][] queries) {
        int n = s.length();
        arr = s.toCharArray();

        pow10 = new long[n + 1];
        pow10[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow10[i] = (pow10[i - 1] * 10) % MOD;
        }

        tree = new Node[4 * n];
        build(1, 0, n - 1);

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            Node res = query(1, 0, n - 1, queries[i][0], queries[i][1]);
            ans[i] = (int) ((res.val * (res.sum % MOD)) % MOD);
        }
        return ans;
    }

    private void build(int idx, int l, int r) {
        if (l == r) {
            int d = arr[l] - '0';
            if (d == 0) {
                tree[idx] = new Node(0, 0, 0);
            } else {
                tree[idx] = new Node(d, 1, d);
            }
            return;
        }

        int mid = (l + r) >> 1;
        build(idx << 1, l, mid);
        build(idx << 1 | 1, mid + 1, r);
        tree[idx] = merge(tree[idx << 1], tree[idx << 1 | 1]);
    }

    private Node query(int idx, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[idx];

        int mid = (l + r) >> 1;
        if (qr <= mid) return query(idx << 1, l, mid, ql, qr);
        if (ql > mid) return query(idx << 1 | 1, mid + 1, r, ql, qr);

        Node left = query(idx << 1, l, mid, ql, qr);
        Node right = query(idx << 1 | 1, mid + 1, r, ql, qr);
        return merge(left, right);
    }

    private Node merge(Node a, Node b) {
        Node res = new Node();
        res.len = a.len + b.len;
        res.sum = a.sum + b.sum;
        res.val = (a.val * pow10[b.len] + b.val) % MOD;
        return res;
    }
}

class Node:
    def __init__(self, val=0, length=0, sm=0):
        self.val = val
        self.len = length
        self.sum = sm


class Solution:
    MOD = 1_000_000_007

    def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        self.arr = list(s)

        self.pow10 = [1] * (n + 1)
        for i in range(1, n + 1):
            self.pow10[i] = (self.pow10[i - 1] * 10) % self.MOD

        self.tree = [Node() for _ in range(4 * n)]
        self.build(1, 0, n - 1)

        ans = []
        for l, r in queries:
            res = self.query(1, 0, n - 1, l, r)
            ans.append((res.val * (res.sum % self.MOD)) % self.MOD)

        return ans

    def build(self, idx, l, r):
        if l == r:
            d = int(self.arr[l])
            if d == 0:
                self.tree[idx] = Node(0, 0, 0)
            else:
                self.tree[idx] = Node(d, 1, d)
            return

        mid = (l + r) // 2
        self.build(idx * 2, l, mid)
        self.build(idx * 2 + 1, mid + 1, r)
        self.tree[idx] = self.merge(self.tree[idx * 2], self.tree[idx * 2 + 1])

    def query(self, idx, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.tree[idx]

        mid = (l + r) // 2
        if qr <= mid:
            return self.query(idx * 2, l, mid, ql, qr)
        if ql > mid:
            return self.query(idx * 2 + 1, mid + 1, r, ql, qr)

        left = self.query(idx * 2, l, mid, ql, qr)
        right = self.query(idx * 2 + 1, mid + 1, r, ql, qr)
        return self.merge(left, right)

    def merge(self, a, b):
        res = Node()
        res.len = a.len + b.len
        res.sum = a.sum + b.sum
        res.val = (a.val * self.pow10[b.len] + b.val) % self.MOD
        return res

class Solution {
    static const int MOD = 1000000007;

    struct Node {
        long long val = 0;
        int len = 0;
        long long sum = 0;
    };

    vector<Node> tree;
    vector<long long> pow10;
    string arr;

public:
    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
        arr = s;
        int n = s.size();

        pow10.assign(n + 1, 1);
        for (int i = 1; i <= n; i++)
            pow10[i] = (pow10[i - 1] * 10) % MOD;

        tree.assign(4 * n, Node());
        build(1, 0, n - 1);

        vector<int> ans;

        for (auto &q : queries) {
            Node res = query(1, 0, n - 1, q[0], q[1]);
            ans.push_back((res.val * (res.sum % MOD)) % MOD);
        }

        return ans;
    }

    void build(int idx, int l, int r) {
        if (l == r) {
            int d = arr[l] - '0';
            if (d == 0)
                tree[idx] = {0, 0, 0};
            else
                tree[idx] = {d, 1, d};
            return;
        }

        int mid = (l + r) / 2;
        build(idx * 2, l, mid);
        build(idx * 2 + 1, mid + 1, r);
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
    }

    Node query(int idx, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return tree[idx];

        int mid = (l + r) / 2;

        if (qr <= mid)
            return query(idx * 2, l, mid, ql, qr);
        if (ql > mid)
            return query(idx * 2 + 1, mid + 1, r, ql, qr);

        Node left = query(idx * 2, l, mid, ql, qr);
        Node right = query(idx * 2 + 1, mid + 1, r, ql, qr);

        return merge(left, right);
    }

    Node merge(Node a, Node b) {
        Node res;
        res.len = a.len + b.len;
        res.sum = a.sum + b.sum;
        res.val = (a.val * pow10[b.len] + b.val) % MOD;
        return res;
    }
};

var sumAndMultiply = function(s, queries) {
    const MOD = 1000000007n;
    const n = s.length;

    const pow10 = new Array(n + 1).fill(0n);
    pow10[0] = 1n;
    for (let i = 1; i <= n; i++) {
        pow10[i] = (pow10[i - 1] * 10n) % MOD;
    }

    class Node {
        constructor(val = 0n, len = 0, sum = 0n) {
            this.val = val;
            this.len = len;
            this.sum = sum;
        }
    }

    const tree = new Array(4 * n);

    function merge(a, b) {
        return new Node(
            (a.val * pow10[b.len] + b.val) % MOD,
            a.len + b.len,
            a.sum + b.sum
        );
    }

    function build(idx, l, r) {
        if (l === r) {
            const d = Number(s[l]);
            if (d === 0)
                tree[idx] = new Node(0n, 0, 0n);
            else
                tree[idx] = new Node(BigInt(d), 1, BigInt(d));
            return;
        }

        const mid = (l + r) >> 1;
        build(idx * 2, l, mid);
        build(idx * 2 + 1, mid + 1, r);
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
    }

    function query(idx, l, r, ql, qr) {
        if (ql <= l && r <= qr) return tree[idx];

        const mid = (l + r) >> 1;

        if (qr <= mid)
            return query(idx * 2, l, mid, ql, qr);
        if (ql > mid)
            return query(idx * 2 + 1, mid + 1, r, ql, qr);

        return merge(
            query(idx * 2, l, mid, ql, qr),
            query(idx * 2 + 1, mid + 1, r, ql, qr)
        );
    }

    build(1, 0, n - 1);

    const ans = [];

    for (const [l, r] of queries) {
        const res = query(1, 0, n - 1, l, r);
        ans.push(Number((res.val * (res.sum % MOD)) % MOD));
    }

    return ans;
};