@Data
public?static?class?Node?{
? ?//區(qū)間起始下標(biāo)
? ?private?int?start;
? ?//區(qū)間結(jié)尾下標(biāo)
? ?private?int?end;
? ?//當(dāng)前區(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 指向線段樹(shù)root節(jié)點(diǎn)的指針，使得root節(jié)點(diǎn)與其余節(jié)點(diǎn)操作保持一致
? ?Node?head;
? ?int?size;
? ?List<Integer>?nums;

? ?//前綴和數(shù)組，便于構(gòu)建線段樹(shù)時(shí)候計(jì)算區(qū)間值，用于初次構(gòu)建輔助
? ?List<Integer>?prefixSum?;
? ?public?void?init(List<Integer>?nums) {
? ? ? ?//初始化一個(gè)頭節(jié)點(diǎn)，便于操作
? ? ? ?this.head?=?new?Node(-1,?-1,?-1);
? ? ? ?this.nums?=?nums;
? ??//初始化前綴和數(shù)組
? ? ? ?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));
? ? ? }
? ??//構(gòu)建線段樹(shù)
? ? ? ?this.build(1,?nums.size());
? ? ? ?size?=?nums.size();
? }

? ?//構(gòu)建線段樹(shù)
? ?public?void?build(int?start,?int?end) {
? ? ??Node?root?=?new?Node(start,?end,?prefixSum.get(end)?-?prefixSum.get(start?-?1));
? ? ?//將頭節(jié)點(diǎn)右子樹(shù)指向root
? ? ??head.right?=?root;
? ? ?//從root開(kāi)始構(gòu)建線段樹(shù)
? ? ??this.madeChild(root,?start,?end);
? }
private?void?madeChild(Node?node,?int?start,?int?end) {
? ? ? ?if?(start?>=?end) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?//分個(gè)左右子樹(shù)，左子樹(shù)取start～mid，右子樹(shù)取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) {
? ? ? ?//深度遍歷線段樹(shù)，找到對(duì)應(yīng)區(qū)間
? ? ? ?if?(start?<?1?||?end?>?size?||?start?>?end) {
? ? ? ? ? ?return?-1;
? ? ? }
? ? ? ?return?dfsFindSectionSum(head.right,?start,?end);
? } ? ?
/**
? ??* 深度遍歷線段樹(shù)結(jié)構(gòu)，分為三種情況
? ??* 1.區(qū)間在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中
? ??* 2.區(qū)間在當(dāng)前節(jié)點(diǎn)的右子樹(shù)中
? ??* 3.左子樹(shù)中一部分，右子樹(shù)中一部分
? ??* @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)) {
? ? ? ? ? ?//在左子樹(shù)中
? ? ? ? ? ?return?this.dfsFindSectionSum(node.left,?start,?end);
? ? ? }
? ? ? ?if?(this.isContain(node.right.start,?node.right.end,?start,?end)) {
? ? ? ? ? ?//包含在右子樹(shù)中
? ? ? ? ? ?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;
? }

//更新線段樹(shù)，將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);
? }