题目链接： 传送门
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 100010; ll arr[4 * N]; int m, n, ca = 1; //注意sum要开long long struct Node { int l, r; ll sum; } tr[4 * N]; //更新操作 void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } //创建线段树 void build(int u, int l, int r) { if(l == r) tr[u] = {l, r, arr[l]}; else { tr[u].l = l; tr[u].r = r; int mid = tr[u].l + tr[u].r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } } //修改操作 void modify(int u, int l, int r) { //单点开方 if(tr[u].l == tr[u].r) { tr[u].sum = sqrt(tr[u].sum); return; } //这一条件很重要，由于多次开放后向下取整，某个数最终会变成1，而当一个区间内的数都为1时，就没必要在再进行修改操作了 if(tr[u].l >= l && tr[u].r <= r && tr[u].sum == tr[u].r - tr[u].l + 1) return; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r); if(r > mid) modify(u << 1 | 1, l, r); pushup(u); } //查询区间和 ll query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum; int mid = tr[u].l + tr[u].r >> 1; ll sum = 0; if (l <= mid) sum += query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } int main() { while(scanf("%d", &n) != EOF) { int s, e, op; memset(tr, 0, sizeof(tr)); for(int i = 1; i <= n; i++) scanf("%lld", &arr[i]); build(1, 1, n); scanf("%d", &m); printf("Case #%d:\n", ca++); while(m--) { scanf("%d%d%d", &op, &s, &e); //这里一个坑点，s和e大小不一定 if(s > e) swap(s, e); if(op == 0) modify(1, s, e); else printf("%lld\n", query(1, s, e)); } printf("\n"); } }这道题是线段树的一个应用，关于线段树的知识点详情请见某大佬博客 然后具体说说这道题的维护，这道题主要时维护区间和，那么首先更新用的pushup就应该写成当父结点等于连个子结点之和。对于查询，每次往下找子结点，不断地返回总和。而对于修改则需要处理到点，但是当某个区间都为1时就不需要处理了，这是一个很重要的优化条件。 在做题时，注意对lld的处理。
