本文主要是介绍POJ-3468 A Simple Problem with Integers 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树区间修改，先用线段树求出每个区间的总和d，对于每次修改，路径上的节点修改总和值d，整个区间都要修改的节点修改加数s，查询的时候解就是区间和加上路径节点（包括表示区间的节点）所有的s*区间长度。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
struct node {int b, e, lc, rc;ll d, s;
}id[422222];
int no;
void init(int u, int b, int e) {
// printf("%d %d %d\n", u, b, e);id[u].b = b;id[u].e = e;id[u].s = 0;if(b == e){scanf("%I64d", &id[u].d);return;}int m = (b + e) >> 1;id[u].lc = no++;id[u].rc = no++;init(id[u].lc, b, m);init(id[u].rc, m + 1, e);id[u].d = id[id[u].lc].d + id[id[u].rc].d;
}
ll query(int u, int b, int e) {
// printf("## %d %d %d\n", u, b, e);if(id[u].b == b && id[u].e == e) {return id[u].d + (e - b + 1) * id[u].s;}int m = (id[u].b + id[u].e) >> 1;if(m >= e) {return id[u].s * (e-b+1) + query(id[u].lc, b, e);}if(b > m)return id[u].s * (e-b+1) + query(id[u].rc, b, e);return id[u].s * (e-b+1) + query(id[u].lc, b, m) + query(id[u].rc, m + 1, e);
}
void update(int u, int b, int e, int c) {if(id[u]. b == b && id[u].e == e) {id[u].s += c;return;}id[u].d += (e-b+1) * c;int m = (id[u].b + id[u].e) >> 1;if(e <= m) {return update(id[u].lc, b, e, c);}if(b > m)return update(id[u].rc, b, e, c);update(id[u].lc, b, m, c);update(id[u].rc, m + 1, e, c);
}
int main() {int n, m, i, j, a, b, c;char ch[10];while(~scanf("%d%d", &n, &m)) {no = 1;init(0, 1, n);for(i = 0; i < m; i++) {scanf("%s", ch);if(ch[0] == 'Q') {scanf("%d%d", &a, &b);printf("%I64d\n", query(0, a, b));}else {scanf("%d%d%d", &a, &b, &c);update(0, a, b, c);}}}return 0;
}这篇关于POJ-3468 A Simple Problem with Integers 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
