洛谷P3372 【模板】线段树 1(树状数组)
程序员文章站
2022-06-28 13:39:02
题意 "题目链接" Sol Get到了这题树状数组的做法,感觉非常nice 区间加:直接差分 区间求和:考虑每一位的贡献 $sum_{i = 1}^x (x+1 i) d_i$ $= sum_{i = 1}^x (x+1)d_i \sum_{i = 1}^x id_i$ $= (x+1) sum_{ ......
题意
sol
get到了这题树状数组的做法,感觉非常nice
区间加:直接差分
区间求和:考虑每一位的贡献
$sum_{i = 1}^x (x+1 - i) d_i$
$= sum_{i = 1}^x (x+1)d_i - \sum_{i = 1}^x id_i$
$= (x+1) sum_{i = 1}^x d_i - \sum_{i = 1}^x id_i$
#include<bits/stdc++.h> #define lb(x) (x & (-x)) #define ll long long #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf; char obuf[1<<24], *o = obuf; void print(ll x) {if(x > 9) print(x / 10); *o++ = x % 10 + '0';} #define os *o++ = '\n'; #define fout fwrite(obuf, o-obuf, 1 , stdout); using namespace std; const int maxn = 1e5 + 10; inline ll read() { char c = getchar(); ll x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m; ll a[maxn], t1[maxn], t2[maxn]; void insert(ll *t, int pos, ll val) { while(pos <= n) t[pos] += val, pos += lb(pos); } ll sum(ll *t, int pos) { ll ans = 0; while(pos) ans += t[pos], pos -= lb(pos); return ans; } ll query(int pos) { return 1ll * (pos + 1) * sum(t1, pos) - sum(t2, pos); } main() { n = read(); m = read(); for(int i = 1; i <= n; i++) a[i] = read(), insert(t1, i, a[i] - a[i - 1]), insert(t2, i, 1ll * i * (a[i] - a[i - 1])); while(m--) { int opt = read(), l = read(), r = read(); if(opt == 1) { ll val = read(); insert(t1, l, val); insert(t1, r + 1, -val); insert(t2, l, 1ll * l * val); insert(t2, r + 1, 1ll * -(r + 1) * val); } else print(query(r) - query(l - 1)), os; } fout; } /* */
上一篇: 张量系列-Tensor(01)
下一篇: 一个可以互相解决前端问题的地方
推荐阅读
-
洛谷-P3372-线段树 1(区间修改,区间求和)
-
洛谷 P3372 线段树【模板1】
-
洛谷P3372 【模板】线段树 1(树状数组)
-
洛谷 P3373 【模板】线段树 2
-
洛谷 - P3810 【模板】三维偏序(陌上花开)(CDQ分治套树状数组)
-
洛谷 P3810 【模板】三维偏序(陌上花开)【cdq 分治】【树状数组】
-
【题解】洛谷P3810【模板】三维偏序(陌上花开)cdq分治+树状数组
-
Codeforces Round #225 (Div. 1) C 树状数组 || 线段树_html/css_WEB-ITnose
-
诈尸了!!! 浅浅浅浅浅浅谈树状数组 + 洛谷P1908 逆序对模板题
-
洛谷P3372 【模板】线段树 1(树状数组)