数据结构-IndexTree结构解析（一）

1.IndexTree

IndexTree解决的问题是什么呢？可以从求前缀和入手这个问题。

1.1前缀和数组

简单封装一个前缀和数组：

package com.xinghai.arr;import java.util.Arrays;/*** 前缀和数组*/
public class PrefixSumArr {// 存储前缀和数据private int[] prefixSumArr;// 存储前缀和数组的长度private final int N;// 构造前缀和public PrefixSumArr(int[] origin) {N = origin.length;prefixSumArr = new int[N];for (int index = 0; index < origin.length; index++) {for (int idx = 0; idx <= index; idx++) {prefixSumArr[index] += origin[idx];}}}// 获取范围求和数据public int getSum(int left, int right) {if (left < 0 || right >= N) {throw new ArrayIndexOutOfBoundsException("索引越界！！！");}if (left > right) {throw new RuntimeException("无效索引");}return prefixSumArr[right] - (left == 0 ? 0 : prefixSumArr[left - 1]);}public int getSum(int right) {return getSum(0, right);}// 操作前缀和数据// 获取前缀和数组中index位置的数据public int get(int index) {return prefixSumArr[index];}// 为前缀和数组中index位置设置对应数据public void set(int index, int value) {if (index >= N || index < 0) {throw new ArrayIndexOutOfBoundsException("索引越界！！！");}// 获取原来索引对应的数据int rawData = prefixSumArr[index] - ((index > 0) ? prefixSumArr[index - 1] : 0);for (int idx = index; idx < N; idx++) {prefixSumArr[idx] += (value - rawData);}}// 为前缀和数组中index位置的数据增加一定值public void add(int index, int value) {if (index >= N || index < 0) {throw new ArrayIndexOutOfBoundsException("索引越界！！！");}for (int idx = index; idx < N; idx++) {prefixSumArr[idx] += value;}}// 打印前缀和数public void printPrefixSumArr() {System.out.println(Arrays.toString(prefixSumArr));}}

分析前缀和数组的时间复杂度。

前缀和数组操作的复杂度主要是分析前缀和数组中的set和add操作。

假设前缀和数组需要更新index位置的数据，那么需要变动的数据量是（N - index）个，即时间复杂度为O(N - index) => 即为O（N），这个时间复杂度还是比较高的，那么有没有一种方式可以降低前缀和数组的时间复杂度，还能达到前缀和数组的效果吗？

Index树就达成这种效果的。

即Index树是为了解决范围求和O（1）的同时，更新数据也能做到O（Log N）的数据结构。

1.2IndexTree是什么？

IndexTree也是使用数组模拟出的树结构（类似于堆结构，线段树）。

这种结构主要的特性是可以完成和前缀和数组一样的效果，并且单点数据更新的时间复杂度为O（log N）

2.解析IndexTree数据结构

掌握IndexTree一定不要尝试去理解发明这个数据结构的人心理路程是怎么样的，因为IndexTree整体设计的比较巧妙，里面的设计很难理解是因为为了发明IndexTree所以诞生这种处理机制，还是因为想到了这种处理机制从而诞生了IndexTree，掌握具体实现有时候比掌握原理其实都重要。

2.1IndexTree的构成

IndexTree构成用语言描述非常复杂，使用手写画图举例的方式可以研究明白IndexTree的构成：

2.2解析单点更新和前缀求和

IndexTree的单点更新和前缀求和会让你感觉十分巧妙，但是不会感觉十分难以理解。

这里我也使用手写的方式呈现出IndexTree是如何构建以及单点更新，范围求和是如何实现的：

其实看完手写笔记，用一句话总结IndexTree就是：IndexTree每个位置的数据都是从自己当前位置index开始向前累加到（index - index最右边的1 + 1）位置。

单点更新也是依赖此实现的，将依赖自己的数据都变量（自己加自己右侧的1，一直加到越界为止）

前缀求和也是依赖IndexTree的特殊结构，先把自己的管的区域（index - index最右侧的1 + 1）- index位置的数据相加，再从index - index最右侧的1开始递归操作，直至越界。

3.详解代码实现

从代码的角度再去理解IndexTree结构，单点更新，范围求和。

3.1构建IndexTree

想要更好的构建IndexTree，必须通透了解IndexTree中每个位置如何借助原数组快速构建IndexTree的。

从手写图中可以总结出：IndexTree中每个位置的累加数据为（index - (index最右侧的1) + 1）- （index）

记住这个公式，使用代码表示出来就是，从当前位置出发向前累加到index - index最右侧的1 + 1的位置。

代码实现：

// 索引树 -> 数组封装
private int[] indexTreeArr;
// IndexTree的长度
private int N;// 初始化Index树
public IndexTree(int[] origin) {N = origin.length + 1;indexTreeArr = new int[N];for (int index = 1; index < N; index++) {int idx = index;idx -= ((idx & -idx) - 1);while (idx <= index) {indexTreeArr[index] += origin[idx++ - 1];}}
}

3.2单点更新

单点更新的核心操作就是从自己开始，一直相加自己最右侧的1，变量位置，更新数据。

// 单点更新
public void add(int index, int value) {if (index < 1 && index >= N) {throw new ArrayIndexOutOfBoundsException("索引越界");}while (index < N) {indexTreeArr[index] += value;index += index & -index;}
}
public void set(int index, int value) {if (index < 1 && index >= N) {throw new ArrayIndexOutOfBoundsException("索引越界");}int oldVal = indexTreeArr[index];while (index < N) {indexTreeArr[index] += (value - oldVal);index += index & -index;}
}

3.3范围求和

范围求和就是从right出发，将当前IndexTree对应的right的数据（即原始数组中right到right - right最右侧的1 + 1）累加后，再将right设定为right - right最右侧的1，继续反复操作，直到越过left为止。

// 分段求和
public int sum(int left, int right) {if (left < 1 || right < 1 || left >= N || right >= N) {throw new ArrayIndexOutOfBoundsException("索引越界！！！");}if (left > right) {throw new RuntimeException("索引错误！！！");}int sum = 0;while (right >= left) {sum += indexTreeArr[right];right -= right & -right;}left -= 1;while (left > 0) {sum -= indexTreeArr[left];left -= left & -left;}return sum;
}public int sum(int right) {return sum(1, right);
}