เซกเมนต์ทรีกับการค้นหาคำตอบแบบไบนารี: คู่หูที่ปลดล็อกโจทย์ระดับยากได้ทั้งชั้น

// เซกเมนต์ทรีแบบวนซ้ำ (iterative) หาค่าน้อยสุดของช่วง กับแก้ทีละช่อง
// ไม่มีการเรียกซ้ำเลย ต้นไม้เก็บในอาเรย์เดียว ใบเริ่มที่ตำแหน่ง sz
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  1 i v = ตั้ง a[i]=v, 2 l r = ถามค่าน้อยสุดช่วง l..r
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    int sz = 1;
    while (sz < n) sz <<= 1;
    const long long INF = (long long)4e18;
    vector<long long> t(2 * sz, INF);           // ใบส่วนเกินต้องเป็น INF ไม่ใช่ 0
    for (int i = 0; i < n; i++) scanf("%lld", &t[sz + i]);
    for (int i = sz - 1; i >= 1; i--) t[i] = min(t[2 * i], t[2 * i + 1]);

    for (int k = 0; k < q; k++) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; long long v; scanf("%d %lld", &i, &v);
            int p = sz + i;
            t[p] = v;
            for (p >>= 1; p >= 1; p >>= 1) t[p] = min(t[2 * p], t[2 * p + 1]);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            // ไต่จากใบขึ้นไป เก็บค่าของฝั่งที่หลุดออกจากคู่ของตัวเอง
            long long res = INF;
            int a = l + sz, b = r + sz + 1;
            while (a < b) {
                if (a & 1) res = min(res, t[a++]);
                if (b & 1) res = min(res, t[--b]);
                a >>= 1;
                b >>= 1;
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}

// เซกเมนต์ทรีที่ปมเก็บ "ค่ามากสุด และมีกี่ตัวที่เท่ากับค่ามากสุด"
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  1 i v = ตั้ง a[i]=v, 2 l r = ถามค่ามากสุดและจำนวนของมันในช่วง
#include <bits/stdc++.h>
using namespace std;

struct Node { long long mx; int cnt; };

// รวมลูกสองตัวเป็นพ่อ ถ้าค่ามากสุดเท่ากันต้องบวกจำนวนของทั้งสองฝั่ง
Node join(const Node& a, const Node& b) {
    if (a.mx > b.mx) return a;
    if (b.mx > a.mx) return b;
    return { a.mx, a.cnt + b.cnt };
}

int n;
vector<Node> t;

void build(const vector<long long>& a, int v, int l, int r) {
    if (l == r) { t[v] = { a[l], 1 }; return; }
    int m = (l + r) / 2;
    build(a, 2 * v, l, m);
    build(a, 2 * v + 1, m + 1, r);
    t[v] = join(t[2 * v], t[2 * v + 1]);
}
void update(int v, int l, int r, int pos, long long val) {
    if (l == r) { t[v] = { val, 1 }; return; }
    int m = (l + r) / 2;
    if (pos <= m) update(2 * v, l, m, pos, val);
    else update(2 * v + 1, m + 1, r, pos, val);
    t[v] = join(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    if (qr <= m) return query(2 * v, l, m, ql, qr);
    if (ql > m) return query(2 * v + 1, m + 1, r, ql, qr);
    return join(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    int q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<long long> a(n);
    for (auto& x : a) scanf("%lld", &x);
    t.assign(4 * n, { LLONG_MIN, 0 });
    build(a, 1, 0, n - 1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; long long v; scanf("%d %lld", &i, &v);
            update(1, 0, n - 1, i, v);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            Node res = query(1, 0, n - 1, l, r);
            printf("%lld %d\n", res.mx, res.cnt);
        }
    }
    return 0;
}

// ห.ร.ม. ของช่วง ต่างจากผลรวมแค่ฟังก์ชันที่ใช้รวมลูกสองตัวเท่านั้น
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  1 i v = ตั้ง a[i]=v, 2 l r = ถาม ห.ร.ม. ของช่วง
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// ค่ากลางของ ห.ร.ม. คือศูนย์ เพราะ gcd(x, 0) เท่ากับ x
// ถ้าเผลอใช้หนึ่งเป็นค่ากลางแบบเดียวกับการคูณ คำตอบจะกลายเป็นหนึ่งทั้งหมด
const ll NEUTRAL = 0;
ll join(ll a, ll b) { return __gcd(a, b); }

int n;
vector<ll> t;

void build(const vector<ll>& a, int v, int l, int r) {
    if (l == r) { t[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(a, 2 * v, l, m);
    build(a, 2 * v + 1, m + 1, r);
    t[v] = join(t[2 * v], t[2 * v + 1]);
}
void update(int v, int l, int r, int pos, ll val) {
    if (l == r) { t[v] = val; return; }
    int m = (l + r) / 2;
    if (pos <= m) update(2 * v, l, m, pos, val);
    else update(2 * v + 1, m + 1, r, pos, val);
    t[v] = join(t[2 * v], t[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return NEUTRAL;
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return join(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    int q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<ll> a(n);
    for (auto& x : a) scanf("%lld", &x);
    t.assign(4 * n, NEUTRAL);
    build(a, 1, 0, n - 1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; ll v; scanf("%d %lld", &i, &v);
            update(1, 0, n - 1, i, v);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            printf("%lld\n", query(1, 0, n - 1, l, r));
        }
    }
    return 0;
}

// เซกเมนต์ทรีที่ปมเก็บสี่ค่า เพื่อตอบ "ผลรวมของช่วงย่อยที่มากที่สุด" ในช่วงที่ถาม
// สี่ค่านั้นคือ ผลรวมทั้งก้อน, ผลรวมที่ดีที่สุดเมื่อเริ่มจากขอบซ้าย, เมื่อจบที่ขอบขวา, และที่ดีที่สุดโดยรวม
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  1 i v = ตั้ง a[i]=v, 2 l r = ถามผลรวมช่วงย่อยที่มากที่สุด (ห้ามว่าง)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node { ll sum, pre, suf, best; };

// หัวใจอยู่ตรงนี้ ช่วงย่อยที่ดีที่สุดของพ่อ มีได้แค่สามแบบ
// อยู่ในลูกซ้ายล้วน อยู่ในลูกขวาล้วน หรือคร่อมรอยต่อ ซึ่งคือหางขวาของซ้าย บวกหัวซ้ายของขวา
Node join(const Node& a, const Node& b) {
    Node c;
    c.sum  = a.sum + b.sum;
    c.pre  = max(a.pre, a.sum + b.pre);
    c.suf  = max(b.suf, b.sum + a.suf);
    c.best = max(max(a.best, b.best), a.suf + b.pre);
    return c;
}
Node leafOf(ll v) { return { v, v, v, v }; }

int n;
vector<Node> t;

void build(const vector<ll>& a, int v, int l, int r) {
    if (l == r) { t[v] = leafOf(a[l]); return; }
    int m = (l + r) / 2;
    build(a, 2 * v, l, m);
    build(a, 2 * v + 1, m + 1, r);
    t[v] = join(t[2 * v], t[2 * v + 1]);
}
void update(int v, int l, int r, int pos, ll val) {
    if (l == r) { t[v] = leafOf(val); return; }
    int m = (l + r) / 2;
    if (pos <= m) update(2 * v, l, m, pos, val);
    else update(2 * v + 1, m + 1, r, pos, val);
    t[v] = join(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    if (qr <= m) return query(2 * v, l, m, ql, qr);
    if (ql > m) return query(2 * v + 1, m + 1, r, ql, qr);
    return join(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    int q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<ll> a(n);
    for (auto& x : a) scanf("%lld", &x);
    t.assign(4 * n, leafOf(0));
    build(a, 1, 0, n - 1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; ll v; scanf("%d %lld", &i, &v);
            update(1, 0, n - 1, i, v);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            printf("%lld\n", query(1, 0, n - 1, l, r).best);
        }
    }
    return 0;
}

// ป้ายค้างชนิด "กำหนดค่าทั้งช่วง" ซึ่งต่างจากชนิดบวก ตรงที่มันทับของเดิมทิ้ง
// จึงต้องดันป้ายลงลูกจริงก่อนลงไปแตะลูกทุกครั้ง
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  1 l r v = กำหนดทุกช่องในช่วงเป็น v, 2 l r = ถามผลรวมของช่วง
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<ll> sum;
vector<ll> mark;      // ค่าที่ถูกกำหนดไว้ทั้งช่วง
vector<char> marked;  // ปมนี้มีป้ายค้างอยู่หรือไม่

void build(const vector<ll>& a, int v, int l, int r) {
    marked[v] = 0;
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(a, 2 * v, l, m);
    build(a, 2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
// ให้ปมรับป้ายค่า val ทั้งช่วง len ช่อง
void apply(int v, int len, ll val) {
    sum[v] = val * (ll)len;
    mark[v] = val;
    marked[v] = 1;
}
// ดันป้ายของ v ลงลูกทั้งสอง แล้วล้างป้ายของตัวเอง
// ถ้าลืมเรียกอันนี้ก่อนลงไปแตะลูก ลูกจะยังถือค่าเก่าที่ถูกทับไปแล้ว
void push(int v, int l, int r) {
    if (!marked[v]) return;
    int m = (l + r) / 2;
    apply(2 * v, m - l + 1, mark[v]);
    apply(2 * v + 1, r - m, mark[v]);
    marked[v] = 0;
}
void assign(int v, int l, int r, int ql, int qr, ll val) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, r - l + 1, val); return; }
    push(v, l, r);
    int m = (l + r) / 2;
    assign(2 * v, l, m, ql, qr, val);
    assign(2 * v + 1, m + 1, r, ql, qr, val);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}

int main() {
    int q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<ll> a(n);
    for (auto& x : a) scanf("%lld", &x);
    sum.assign(4 * n, 0); mark.assign(4 * n, 0); marked.assign(4 * n, 0);
    build(a, 1, 0, n - 1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int l, r; ll v; scanf("%d %d %lld", &l, &r, &v);
            assign(1, 0, n - 1, l, r, v);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            printf("%lld\n", query(1, 0, n - 1, l, r));
        }
    }
    return 0;
}

// บวกทั้งช่วง ถามค่ามากสุดของช่วง เขียนแบบดันป้ายลงลูกจริง เพื่อให้เห็นรูปมาตรฐาน
// (โค้ดหลักของบทนี้ใช้อีกรูปหนึ่งคือไม่ดันป้าย แต่บวกป้ายสะสมระหว่างทางแทน)
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  1 l r v = บวก v ทั้งช่วง, 2 l r = ถามค่ามากสุดของช่วง
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<ll> mx, lz;

void build(const vector<ll>& a, int v, int l, int r) {
    lz[v] = 0;
    if (l == r) { mx[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(a, 2 * v, l, m);
    build(a, 2 * v + 1, m + 1, r);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
void apply(int v, ll val) { mx[v] += val; lz[v] += val; }
void push(int v) {
    if (lz[v] == 0) return;
    apply(2 * v, lz[v]);
    apply(2 * v + 1, lz[v]);
    lz[v] = 0;
}
void add(int v, int l, int r, int ql, int qr, ll val) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, val); return; }
    push(v);
    int m = (l + r) / 2;
    add(2 * v, l, m, ql, qr, val);
    add(2 * v + 1, m + 1, r, ql, qr, val);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return LLONG_MIN;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) / 2;
    return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    int q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<ll> a(n);
    for (auto& x : a) scanf("%lld", &x);
    mx.assign(4 * n, 0); lz.assign(4 * n, 0);
    build(a, 1, 0, n - 1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int l, r; ll v; scanf("%d %d %lld", &l, &r, &v);
            add(1, 0, n - 1, l, r, v);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            printf("%lld\n", query(1, 0, n - 1, l, r));
        }
    }
    return 0;
}

// ต้นไม้ที่ทุกปมเก็บ "อาเรย์ย่อยของช่วงนั้น เรียงจากน้อยไปมาก"
// ตอบคำถาม "ค่าที่น้อยที่สุดที่ยังไม่น้อยกว่า x ในช่วง l ถึง r" ได้ในเวลา log n ยกกำลังสอง
// ตัวอาเรย์แก้ไม่ได้ แลกกับความง่าย
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  l r x
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> t;   // t[v] คือรายการที่เรียงแล้วของช่วงที่ปม v ดูแล

void build(const vector<int>& a, int v, int l, int r) {
    if (l == r) { t[v] = { a[l] }; return; }
    int m = (l + r) / 2;
    build(a, 2 * v, l, m);
    build(a, 2 * v + 1, m + 1, r);
    // รวมสองรายการที่เรียงแล้วเข้าด้วยกัน คือขั้นตอน merge ของการเรียงแบบแบ่งครึ่ง
    t[v].resize(t[2 * v].size() + t[2 * v + 1].size());
    merge(t[2 * v].begin(), t[2 * v].end(), t[2 * v + 1].begin(), t[2 * v + 1].end(), t[v].begin());
}
const int NONE = INT_MAX;
int query(int v, int l, int r, int ql, int qr, int x) {
    if (qr < l || r < ql) return NONE;
    if (ql <= l && r <= qr) {
        // ในรายการที่เรียงแล้ว ตัวแรกที่ไม่น้อยกว่า x หาได้ด้วยการค้นหาแบบไบนารีครั้งเดียว
        auto it = lower_bound(t[v].begin(), t[v].end(), x);
        return it == t[v].end() ? NONE : *it;
    }
    int m = (l + r) / 2;
    return min(query(2 * v, l, m, ql, qr, x), query(2 * v + 1, m + 1, r, ql, qr, x));
}

int main() {
    int q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<int> a(n);
    for (auto& x : a) scanf("%d", &x);
    t.assign(4 * n, {});
    build(a, 1, 0, n - 1);
    while (q--) {
        int l, r, x; scanf("%d %d %d", &l, &r, &x);
        int got = query(1, 0, n - 1, l, r, x);
        printf("%d\n", got == NONE ? -1 : got);
    }
    return 0;
}

// ต้นไม้ที่จำอดีตได้ ใช้ตอบ "ค่าที่เล็กเป็นอันดับที่ k ในช่วง l ถึง r"
// แนวคิด: สร้างต้นไม้นับจำนวนของค่าทีละช่อง เก็บไว้ทุกเวอร์ชัน
// จำนวนของค่าในช่วง l ถึง r ก็คือ เวอร์ชันที่ r ลบเวอร์ชันที่ l-1 ทีละปม
// แล้วเดินลงต้นไม้ด้วยผลต่างนั้น
// อินพุต: n q, อาเรย์, แล้ว q บรรทัด  l r k
#include <bits/stdc++.h>
using namespace std;

struct Node { int left, right, cnt; };
vector<Node> t;
vector<int> root;

int newNode(int left, int right, int cnt) {
    t.push_back({ left, right, cnt });
    return (int)t.size() - 1;
}
int buildEmpty(int l, int r) {
    if (l == r) return newNode(0, 0, 0);
    int m = (l + r) / 2;
    int a = buildEmpty(l, m), b = buildEmpty(m + 1, r);
    return newNode(a, b, 0);
}
// เพิ่มหนึ่งที่ตำแหน่ง pos โดยไม่แก้ปมเดิมเลย สร้างปมใหม่แค่เส้นทางเดียวจากรากลงใบ
int insert(int prev, int l, int r, int pos) {
    if (l == r) return newNode(0, 0, t[prev].cnt + 1);
    int m = (l + r) / 2;
    if (pos <= m) {
        int nl = insert(t[prev].left, l, m, pos);
        return newNode(nl, t[prev].right, t[nl].cnt + t[t[prev].right].cnt);
    }
    int nr = insert(t[prev].right, m + 1, r, pos);
    return newNode(t[prev].left, nr, t[t[prev].left].cnt + t[nr].cnt);
}
// เดินลงพร้อมกันสองเวอร์ชัน ผลต่างของจำนวนคือจำนวนที่อยู่ในช่วงที่ถามจริง
int kth(int lo, int hi, int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) / 2;
    int leftCnt = t[t[hi].left].cnt - t[t[lo].left].cnt;
    if (leftCnt >= k) return kth(t[lo].left, t[hi].left, l, m, k);
    return kth(t[lo].right, t[hi].right, m + 1, r, k - leftCnt);
}

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<int> a(n);
    for (auto& x : a) scanf("%d", &x);
    // บีบค่าให้เป็นลำดับที่ เพราะต้นไม้นับจำนวนต้องมีขนาดเท่ากับจำนวนค่าที่ต่างกัน
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int V = (int)vals.size();

    t.clear(); t.push_back({ 0, 0, 0 });
    root.assign(n + 1, 0);
    root[0] = buildEmpty(0, V - 1);
    for (int i = 0; i < n; i++) {
        int id = (int)(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
        root[i + 1] = insert(root[i], 0, V - 1, id);
    }
    while (q--) {
        int l, r, k; scanf("%d %d %d", &l, &r, &k);
        printf("%d\n", vals[kth(root[l], root[r + 1], 0, V - 1, k)]);
    }
    return 0;
}

// ต้นไม้ที่งอกเฉพาะกิ่งที่ถูกใช้ ใช้กับช่วงดัชนีที่ใหญ่จนสร้างทั้งต้นไม่ไหว เช่นถึงหนึ่งพันล้าน
// ปมลูกไม่ได้อยู่ที่ 2v กับ 2v+1 อีกแล้ว แต่เก็บเป็นหมายเลขปมที่สร้างเมื่อถูกเรียกใช้ครั้งแรก
// อินพุต: q แล้ว q บรรทัด  1 i v = บวก v ที่ตำแหน่ง i, 2 l r = ถามผลรวมช่วง  (0 <= i < 1e9)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int LIMIT = 1000000000;
struct Node { int left = 0, right = 0; ll sum = 0; };
vector<Node> t(1);   // ปมหมายเลข 0 คือปมว่าง ใช้แทน "ยังไม่มีลูก"

int makeNode() { t.push_back(Node()); return (int)t.size() - 1; }

// คืนหมายเลขปมกลับไปให้พ่อเก็บ ห้ามรับเป็น int& ที่ชี้เข้าไปใน t
// เพราะ makeNode ทำให้ t ขยายตัวและย้ายที่ อ้างอิงเดิมจะชี้ไปที่หน่วยความจำที่ไม่ใช่ของมันแล้ว
int update(int v, int l, int r, int pos, ll val) {
    if (v == 0) v = makeNode();       // งอกตรงนี้ เฉพาะตอนที่จำเป็นจริง
    t[v].sum += val;
    if (l == r) return v;
    int m = l + (r - l) / 2;
    if (pos <= m) { int c = update(t[v].left, l, m, pos, val); t[v].left = c; }
    else { int c = update(t[v].right, m + 1, r, pos, val); t[v].right = c; }
    return v;
}
ll query(int v, int l, int r, int ql, int qr) {
    if (v == 0 || qr < l || r < ql) return 0;   // กิ่งที่ไม่เคยงอก แปลว่าไม่มีค่าอะไรอยู่เลย
    if (ql <= l && r <= qr) return t[v].sum;
    int m = l + (r - l) / 2;
    return query(t[v].left, l, m, ql, qr) + query(t[v].right, m + 1, r, ql, qr);
}

int main() {
    int q;
    if (scanf("%d", &q) != 1) return 0;
    int root = 0;
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; ll v; scanf("%d %lld", &i, &v);
            root = update(root, 0, LIMIT, i, v);
        } else {
            int l, r; scanf("%d %d", &l, &r);
            printf("%lld\n", query(root, 0, LIMIT, l, r));
        }
    }
    return 0;
}

// ต้นไม้สองมิติ ต้นนอกแบ่งตามแถว ทุกปมของต้นนอกมีต้นไม้ของตัวเองที่แบ่งตามคอลัมน์
// ตอบผลรวมของสี่เหลี่ยมได้ในเวลา log n คูณ log m
// อินพุต: n m q, ตาราง n แถว m หลัก, แล้ว q บรรทัด
//   1 r c v = ตั้งช่อง (r,c) เป็น v, 2 r1 c1 r2 c2 = ถามผลรวมของสี่เหลี่ยม
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m;
vector<vector<ll>> t;   // t[vx][vy]

void buildY(const vector<vector<ll>>& g, int vx, int lx, int rx, int vy, int ly, int ry) {
    if (ly == ry) {
        if (lx == rx) t[vx][vy] = g[lx][ly];
        else t[vx][vy] = t[2 * vx][vy] + t[2 * vx + 1][vy];
        return;
    }
    int my = (ly + ry) / 2;
    buildY(g, vx, lx, rx, 2 * vy, ly, my);
    buildY(g, vx, lx, rx, 2 * vy + 1, my + 1, ry);
    t[vx][vy] = t[vx][2 * vy] + t[vx][2 * vy + 1];
}
void buildX(const vector<vector<ll>>& g, int vx, int lx, int rx) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        buildX(g, 2 * vx, lx, mx);
        buildX(g, 2 * vx + 1, mx + 1, rx);
    }
    buildY(g, vx, lx, rx, 1, 0, m - 1);
}
void updateY(int vx, int lx, int rx, int vy, int ly, int ry, int y, ll val) {
    if (ly == ry) {
        if (lx == rx) t[vx][vy] = val;
        else t[vx][vy] = t[2 * vx][vy] + t[2 * vx + 1][vy];
        return;
    }
    int my = (ly + ry) / 2;
    if (y <= my) updateY(vx, lx, rx, 2 * vy, ly, my, y, val);
    else updateY(vx, lx, rx, 2 * vy + 1, my + 1, ry, y, val);
    t[vx][vy] = t[vx][2 * vy] + t[vx][2 * vy + 1];
}
void updateX(int vx, int lx, int rx, int x, int y, ll val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx) updateX(2 * vx, lx, mx, x, y, val);
        else updateX(2 * vx + 1, mx + 1, rx, x, y, val);
    }
    updateY(vx, lx, rx, 1, 0, m - 1, y, val);
}
ll queryY(int vx, int vy, int ly, int ry, int qy1, int qy2) {
    if (qy2 < ly || ry < qy1) return 0;
    if (qy1 <= ly && ry <= qy2) return t[vx][vy];
    int my = (ly + ry) / 2;
    return queryY(vx, 2 * vy, ly, my, qy1, qy2) + queryY(vx, 2 * vy + 1, my + 1, ry, qy1, qy2);
}
ll queryX(int vx, int lx, int rx, int qx1, int qx2, int qy1, int qy2) {
    if (qx2 < lx || rx < qx1) return 0;
    if (qx1 <= lx && rx <= qx2) return queryY(vx, 1, 0, m - 1, qy1, qy2);
    int mx = (lx + rx) / 2;
    return queryX(2 * vx, lx, mx, qx1, qx2, qy1, qy2)
         + queryX(2 * vx + 1, mx + 1, rx, qx1, qx2, qy1, qy2);
}

int main() {
    int q;
    if (scanf("%d %d %d", &n, &m, &q) != 3) return 0;
    vector<vector<ll>> g(n, vector<ll>(m));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%lld", &g[i][j]);
    t.assign(4 * n, vector<ll>(4 * m, 0));
    buildX(g, 1, 0, n - 1);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int r, c; ll v; scanf("%d %d %lld", &r, &c, &v);
            updateX(1, 0, n - 1, r, c, v);
        } else {
            int r1, c1, r2, c2; scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
            printf("%lld\n", queryX(1, 0, n - 1, r1, r2, c1, c2));
        }
    }
    return 0;
}