Xét trên Segment Tree, với mỗi nút id, quản lý đoạn ~[l,r]~ ta lưu ~6~ thông tin sau:

• left_odd: Số lượng dãy con khác rỗng ~[l,R] (R <= r)~ có tổng là số lẻ
• left_even: Số lượng dãy con khác rỗng ~[l,R] (R <= r)~ có tổng là số chẵn
• right_odd: Số lượng dãy con khác rỗng ~[L,r] (L >= l)~ có tổng là số lẻ
• right_even: Số lượng dãy con khác rỗng ~[L,r] (L >= l)~ có tổng là số chẵn
• even_total: Tổng số lượng dãy con có tổng chẵn trong đoạn ~[l,r]~
• sum: Tổng của đoạn ~[l,r]~

Khi thực hiện thao tác kết hợp 2 nút của cây phân đoạn. Gọi par là nút cha, left là nút con trái và right là nút con phải thì:

par.sum = left.sum + right.sum;

• Nếu left.sum là số lẻ:

par.left_odd = left.left_odd + right.left_even
par.left_even = left.left_even + right.left_odd

• Ngược lại thì:

par.left_odd = left.left_odd + right.left_odd
par.left_even = left.left_even + right.left_even

• Nếu right.sum là số lẻ:

par.right_odd = right.right_odd + left.right_even
par.right_even = right.right_even + left.right_odd

• Ngược lại thì:

par.right_odd = right.right_odd + left.right_odd
par.right_even = right.right_even + left.right_even

• Cuối cùng ta có:

par.even_total = left.even_total + right.even_total + left.right_even * right.left_even + left.right_odd * right.left_odd

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

const int N = 1e5 + 5;

struct Node{
    int ans, sum;
    int podd, peven, sodd, seven;
} ST[N * 4];
int n, q, a[N];

Node merge(Node& l, Node& r) {
    Node res;
    res.sum = (l.sum + r.sum) & 1;
    res.ans = l.ans + r.ans + l.seven * r.peven + l.sodd * r.podd;

    res.podd = l.podd + (l.sum ? r.peven : r.podd);
    res.peven = l.peven + (l.sum ? r.podd : r.peven);
    res.sodd = r.sodd + (r.sum ? l.seven : l.sodd);
    res.seven = r.seven + (r.sum ? l.sodd : l.seven);

    return res;
}

void build(int id, int l, int r) {
    if (l == r) {
        ST[id].ans = (a[l] ^ 1);
        ST[id].sum = a[l];

        ST[id].podd = ST[id].sodd = a[l];
        ST[id].peven = ST[id].seven = (a[l] ^ 1);
        return;
    }

    int m = (l + r) >> 1;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    ST[id] = merge(ST[id * 2], ST[id * 2 + 1]);
}

void update(int id, int l, int r, int pos, int val) {
    if (l == r) {
        ST[id].ans = (a[l] ^ 1);
        ST[id].sum = a[l];

        ST[id].podd = ST[id].sodd = a[l];
        ST[id].peven = ST[id].seven = (a[l] ^ 1);
        return;
    }

    int m = (l + r) >> 1;
    if (pos <= m) update(id * 2, l, m, pos, val);
    else update(id * 2 + 1, m + 1, r, pos, val);

    ST[id] = merge(ST[id * 2], ST[id * 2 + 1]);
}

void query(int id, int l, int r, int tl, int tr, Node& res) {
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr) {
        if (l == tl) res = ST[id];
        else res = merge(res, ST[id]);
        return;
    }

    int m = (l + r) >> 1;
    query(id * 2, l, m, tl, tr, res);
    query(id * 2 + 1, m + 1, r, tl, tr, res);
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> q;
    for1(i,1,n) {
        cin >> a[i];
        a[i] &= 1;
    }

    build(1, 1, n);
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            a[x] = (y & 1);
            update(1, 1, n, x, y);
        }
        else {
            int l, r;
            cin >> l >> r;
            Node res;
            query(1, 1, n, l, r, res);
            cout << res.ans << "\n";
        }
    }

}