@Data
public?static?class?Node?{
? ?//區(qū)間起始下標
? ?private?int?start;
? ?//區(qū)間結尾下標
? ?private?int?end;
? ?//當前區(qū)間和值
? ?private?int?value;
? ?private?Node?left;
? ?private?Node?right;
? ?Node(int?start,?int?end,?int?value) {
? ? ? ?this.start?=?start;
? ? ? ?this.end?=?end;
? ? ? ?this.value?=?value;
? }
}

//head 指向線段樹root節(jié)點的指針，使得root節(jié)點與其余節(jié)點操作保持一致
? ?Node?head;
? ?int?size;
? ?List<Integer>?nums;

? ?//前綴和數組，便于構建線段樹時候計算區(qū)間值，用于初次構建輔助
? ?List<Integer>?prefixSum?;
? ?public?void?init(List<Integer>?nums) {
? ? ? ?//初始化一個頭節(jié)點，便于操作
? ? ? ?this.head?=?new?Node(-1,?-1,?-1);
? ? ? ?this.nums?=?nums;
? ??//初始化前綴和數組
? ? ? ?prefixSum?=?new?ArrayList<>(nums.size());
? ? ? ?prefixSum.add(0);
? ? ? ?for?(int?i?=?0;?i?<?nums.size() ;?i++) {
? ? ? ? ? ?prefixSum.add(prefixSum.get(prefixSum.size()?-?1)?+?nums.get(i));
? ? ? }
? ??//構建線段樹
? ? ? ?this.build(1,?nums.size());
? ? ? ?size?=?nums.size();
? }

? ?//構建線段樹
? ?public?void?build(int?start,?int?end) {
? ? ??Node?root?=?new?Node(start,?end,?prefixSum.get(end)?-?prefixSum.get(start?-?1));
? ? ?//將頭節(jié)點右子樹指向root
? ? ??head.right?=?root;
? ? ?//從root開始構建線段樹
? ? ??this.madeChild(root,?start,?end);
? }
private?void?madeChild(Node?node,?int?start,?int?end) {
? ? ? ?if?(start?>=?end) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?//分個左右子樹，左子樹取start～mid，右子樹取mid+1～end
? ? ? ?int?mid?=?start?+?((end?-?start)?>>?1);
? ? ? ?if?(start?<=?mid) {
? ? ? ? ? ?Node?left?=?new?Node(start,?mid,?prefixSum.get(mid)?-?prefixSum.get(start?-?1));
? ? ? ? ? ?node.left?=?left;
? ? ? ? ? ?madeChild(left,?start,?mid);
? ? ? }
? ? ? ?if?(mid?+?1?<=?end) {
? ? ? ? ? ?Node?right?=?new?Node(mid?+?1,?end,?prefixSum.get(end)?-?prefixSum.get(mid));
? ? ? ? ? ?node.right?=?right;
? ? ? ? ? ?madeChild(right,?mid?+?1,?end);
? ? ? }
? }

//求解區(qū)間和
? ?public?int?findSectionSum(int?start,?int?end) {
? ? ? ?//深度遍歷線段樹，找到對應區(qū)間
? ? ? ?if?(start?<?1?||?end?>?size?||?start?>?end) {
? ? ? ? ? ?return?-1;
? ? ? }
? ? ? ?return?dfsFindSectionSum(head.right,?start,?end);
? } ? ?
/**
? ??* 深度遍歷線段樹結構，分為三種情況
? ??* 1.區(qū)間在當前節(jié)點的左子樹中
? ??* 2.區(qū)間在當前節(jié)點的右子樹中
? ??* 3.左子樹中一部分，右子樹中一部分
? ??* @param node
? ??* @param start
? ??* @param end
? ??* @return
? ??*/
? ?private?int?dfsFindSectionSum(Node?node,?int?start,?int?end) {
? ? ? ?if?(node.start?==?start?&&?node.end?==?end) {
? ? ? ? ? ?//找到區(qū)間
? ? ? ? ? ?return?node.value;
? ? ? }
? ? ? ?if?(this.isContain(node.left.start,?node.left.end,?start,?end)) {
? ? ? ? ? ?//在左子樹中
? ? ? ? ? ?return?this.dfsFindSectionSum(node.left,?start,?end);
? ? ? }
? ? ? ?if?(this.isContain(node.right.start,?node.right.end,?start,?end)) {
? ? ? ? ? ?//包含在右子樹中
? ? ? ? ? ?return?this.dfsFindSectionSum(node.right,?start,?end);
? ? ? }
? ? ? ?//左邊一部分，右邊一部分
? ? ? ?return?this.dfsFindSectionSum(node.left,?start,?node.left.end)?+?this.dfsFindSectionSum(node.right,?node.right.start,?end);
? }
? ?/**
? ??* 判斷區(qū)間[start2, end2]是否包含在[start1, end1]中
? ??* @param start1
? ??* @param end1
? ??* @param start2
? ??* @param end2
? ??* @return
? ??*/
? ?private?boolean?isContain(int?start1,?int?end1,?int?start2,?int?end2){
? ? ? ?return?start2?>=?start1?&&?end2?<=?end1;
? }

//更新線段樹，將index位置的值更新為value，需要更新沿路的值
? ?public?void?update(int?index,?int?value) {
? ? ? ?Node?root?=?head.right;
? ? ? ?while?(null?!=?root) {
? ? ? ? ? ?if?(index?>=?root.start?&&?index?<=?root.end) {
? ? ? ? ? ? ? ?root.value?+=?value?-?nums.get(index?-?1);
? ? ? ? ? }
? ? ? ? ? ?int?mid?=?root.start?+?((root.end?-?root.start)?>>?1);
? ? ? ? ? ?if?(index?<=?mid) {
? ? ? ? ? ? ? ?root?=?root.left;
? ? ? ? ? ? ? ?continue;
? ? ? ? ? }
? ? ? ? ? ?root?=?root.right;
? ? ? }
? ? ? ?nums.set(index?-?1,?value);
? }