首页 > 代码库 > poj 3468【线段树】
poj 3468【线段树】
题意：给定Q（1<=Q<=100000）个数A1，A2…AQ，以及可能多次进行的两个操作
1）对某个区间Ai……Aj的每个数都加n（n可变）
2）对某个区间Ai……Aj的数求和
分析：
树结点只存和，会导致每次加数时都要更新到叶子节点，速度太慢(O(nlog(n)))，这是必须避免的
1.在增加时，如果要加的区间正好覆盖一个节点，则增加其节点的Inc值，不再往下走，否则要更新nSum（加上本次增量）
再将增量往下传。这样更新的复杂度就是O(log(n))
2.在查询时，如果待查区间不是正好覆盖一个节点，就将节点的Inc往下带，然后将Inc代表的所有增量累加到nSum上后将
Inc清0，接下来再往下查询。Inc往下带的过程也是区间分解过程，复杂度也是O(log(n))
#include<algorithm> #include<cstdio>#include<vector>#include<string> #include<string.h> #include<iostream>using namespace std;typedef long long LL;const int INF = 0x7FFFFFFF;const int maxn = 1e3 + 10;struct CNode{ int L, R; CNode *pLeft, *pRight; long long nSum;//原来的和 long long Inc;//增量c的累加};CNode Tree[200010];//2倍叶子节点数目就够int nCount = 0;int Mid(CNode*pRoot){ return (pRoot->L + pRoot->R) / 2;}void BuildTree(CNode *pRoot, int L, int R){ pRoot->L = L; pRoot->R = R; pRoot->nSum = 0; pRoot->Inc = 0; if (L == R) return; nCount++; pRoot->pLeft = Tree + nCount; nCount++; pRoot->pRight = Tree + nCount; BuildTree(pRoot->pLeft, L, (L + R) / 2); BuildTree(pRoot->pRight, (L + R) / 2 + 1, R);}void Insert(CNode *pRoot, int i, int v){ if (pRoot->L == i&&pRoot->R == i) { pRoot->nSum = v; return; } pRoot->nSum += v;//累加和 if (i <= Mid(pRoot)) Insert(pRoot->pLeft, i, v); else Insert(pRoot->pRight, i, v); }void Add(CNode * pRoot, int a, int b, long long c){ if (pRoot->L == a&&pRoot->R == b) { pRoot->Inc += c; return; } pRoot->nSum += c*(b - a + 1); if (b <= (pRoot->L + pRoot->R) / 2) Add(pRoot->pLeft, a, b, c); else if (a >= (pRoot->L + pRoot->R) / 2 + 1) Add(pRoot->pRight, a, b, c); else { Add(pRoot->pLeft, a, (pRoot->L + pRoot->R) / 2, c); Add(pRoot->pRight, (pRoot->L + pRoot->R) / 2 + 1, b, c); } }long long QuerynSum(CNode * pRoot, int a, int b){ if (pRoot->L == a&&pRoot->R == b) return pRoot->nSum + (pRoot->R - pRoot->L + 1)*pRoot->Inc; pRoot->nSum += (pRoot->R - pRoot->L + 1)*pRoot->Inc; Add(pRoot->pLeft, pRoot->L, Mid(pRoot), pRoot->Inc); Add(pRoot->pRight, Mid(pRoot) + 1, pRoot->R, pRoot->Inc); pRoot->Inc = 0; if (b <= Mid(pRoot)) return QuerynSum(pRoot->pLeft, a, b); else if (a >= Mid(pRoot) + 1) return QuerynSum(pRoot->pRight, a, b); else { return QuerynSum(pRoot->pLeft, a, Mid(pRoot)) + QuerynSum(pRoot->pRight, Mid(pRoot) + 1, b); }}int main(){ int n, q, a, b, c; char cmd[10]; scanf("%d%d", &n, &q); int i, j, k; nCount = 0; BuildTree(Tree, 1, n); for (i = 1; i <= n;i++) { scanf("%d", &a); Insert(Tree, i, a); } for (i = 0; i < q; i++) { scanf("%s", cmd); if (cmd[0]==‘C‘) { scanf("%d%d%d", &a, &b, &c); Add(Tree, a, b, c); } else { scanf("%d%d", &a, &b); printf("%I64d\n", QuerynSum(Tree, a, b)); } } return 0;}poj 3468【线段树】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。