Untitled
unknown
c_cpp
a month ago
1.9 kB
1
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define Achilles ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); typedef long long ll; #define M 1000000007 #define pp push_back const int N = (1 << 18); struct Node { ll sum; Node() { sum = 0; } }; int a[N], n, q; Node seg[N]; ll merge(Node &l, Node &r) { return l.sum + r.sum; } void build(int ns = 0, int ne = n - 1, int ni = 0) { if (ns == ne) { seg[ni].sum = a[ns]; return; } int l = 2 * ni + 1, r = l + 1, m = ns + (ne - ns) / 2; build(ns, m, l); build(m + 1, ne, r); seg[ni].sum = merge(seg[l], seg[r]); } ll query(int qs, int qe, int ns = 0, int ne = n - 1, int ni = 0) { if (qe < ns || ne < qs || seg[ni].sum == 0) return 0; if (qs <= ns && ne <= qe) return seg[ni].sum; int l = 2 * ni + 1, r = l + 1, m = ns + (ne - ns) / 2; ll ans_l = query(qs, qe, ns, m, l); ll ans_r = query(qs, qe, m + 1, ne, r); return (ans_l + ans_r); } void update(int idx, ll val, int ns = 0, int ne = n - 1, int ni = 0) { if (idx < ns || ne < idx) return; if (ns == ne) { seg[ni].sum = val; return; } int l = 2 * ni + 1, r = l + 1, m = ns + (ne - ns) / 2; update(idx, val, ns, m, l); update(idx, val, m + 1, ne, r); seg[ni].sum = merge(seg[l], seg[r]); } void func() { cin >> n >> q; for (int i = 0; i < n; ++i) { cin >> a[i]; } build(); int t; while (q--) { cin >> t; if (t == 1) { int idx, val; cin >> idx >> val; update(idx, val); } else { int l, r; cin >> l >> r; r--; cout << query(l, r) << '\n'; } } } int main() { Achilles #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t = 1; // cin >> t; while (t--) { func(); } }
Leave a Comment