POJ 3468 【线段树】

区间更新区间求和

思想:懒处理,对于区间更新不需要将更新具体到叶子结点,只在需要更新的时候,,再细化处理。

代码:

import java.util.Scanner;class SegmentTree{class Node{int left;int right;long sum;long addValue;}private long[] leafNodes;private int leafNodesNum;private Node[] treeNodes;public SegmentTree(long[] leafNodes, int leafNodesNum) {this.leafNodes = leafNodes;this.leafNodesNum = leafNodesNum;this.treeNodes = new Node[this.leafNodesNum * 4];buildTree(1, 1, this.leafNodesNum);}) {this.treeNodes[root] = new Node();this.treeNodes[root].left = left;this.treeNodes[root].right = right;if(left == right) {this.treeNodes[root].sum = this.leafNodes[left – 1];}else {int mid = (left + right) / 2;this.treeNodes[root].sum = buildTree(root * 2, left, mid) + buildTree(root * 2 + 1, mid + 1, right);}return this.treeNodes[root].sum;}, long addValue) {add(1, left, right, addValue);}, long addValue) {this.treeNodes[root].sum += (right – left + 1) * addValue;if(this.treeNodes[root].left == left && this.treeNodes[root].right == right) {this.treeNodes[root].addValue += addValue;}else {pushDown(root);int mid = (this.treeNodes[root].left + this.treeNodes[root].right) / 2;if(right <= mid) {add(root * 2, left, right, addValue);}else if(left > mid) {add(root * 2 + 1, left, right, addValue);}else {add(root * 2, left, mid, addValue);add(root * 2 + 1, mid + 1, right, addValue);}}}private void pushDown(int root) {int mid = (this.treeNodes[root].left + this.treeNodes[root].right) / 2;add(root * 2, this.treeNodes[root].left, mid, this.treeNodes[root].addValue);add(root * 2 + 1, mid + 1, this.treeNodes[root].right, this.treeNodes[root].addValue);this.treeNodes[root].addValue = 0;}) {return sum(1, left, right);}) {if(this.treeNodes[root].left == left && this.treeNodes[root].right == right) {return this.treeNodes[root].sum;}else {pushDown(root);int mid = (this.treeNodes[root].left + this.treeNodes[root].right) / 2;if(right <= mid) {return sum(root * 2, left, right);}else if(left > mid) {return sum(root * 2 + 1, left, right);}else {return sum(root * 2, left, mid) + sum(root * 2 + 1, mid + 1, right);}}}}public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);int N, Q;int a, b, c;long[] A = new long[100000 + 10];while(cin.hasNext()) {N = cin.nextInt();Q = cin.nextInt();for(int i = 0; i < N; i ++) {A[i] = cin.nextLong();}SegmentTree st = new SegmentTree(A, N);for(int i = 0; i < Q; i ++) {String oper = cin.next();if(oper.equals(“Q”)) {a = cin.nextInt();b = cin.nextInt();System.out.println(st.sum(a, b));}else {a = cin.nextInt();b = cin.nextInt();c = cin.nextInt();st.add(a, b, c);}}}}}

可以一个人,可以几个人,一起放松那劳累的心情或者劳累自己的身体,

POJ 3468 【线段树】

相关文章:

你感兴趣的文章:

标签云: