Tree array + discretization

Advantages of tree array

• Quickly modify a number $O(logn)$
• Quickly find the prefix sum $O(logn)$

Compare the original array ：

• Modify a number $O(1)$
• Find the prefix and $O(n)$

Compare prefix and array

• Modify a number $O(n)$
• Find the prefix and $O(1)$

Implementation of tree array

Principle see blog ： The main idea is to use binary , Divide the original array into blocks , Then modify and sum it
There are two main operations ：

• Modify the operating ： In a certain position +c, In the current block and subsequent blocks +c

public void add(int x, int c) {
    
	for(int i = x; i <= n; i += lowbit(i)) {
    
		tr[i] += c;
	}
}

• Summation operation ： take $a[1\sim x]$ Sum of the elements of

public int sum(int x) {
    
	int res = 0;
	for(int i = x; i >= 1; i -= lowbit(i)) {
    
		res += tr[i];
	}
}

( among ,lowbit(x) Is to seek x The last bit in the binary representation of 1, namely x&(-x))

• But the topic often appears n A lot of things , for example $n>10^6$, Or there are negative numbers , Then the tree array will be very large or the subscript will be out of bounds , Cause memory overflow . So at this time, we need to discretize the original array . Discretization has two steps , They are sort + duplicate removal , This can be achieved with the help of ordered sets . But after using ordered sets , The corresponding number subscript cannot be determined quickly , At this time, we need to use hash table , Map numbers in an ordered set to [1,n] On , At this point, the requirements of tree array are met .（ Discrete implementation ： Ordered set + Hashtable ）

Example

LeetCode327. The number of interval sums

Give you an array of integers $nums$ And two integers $lower$ and $upper$. In the array , The value is in the range $[lower,upper]$ （ contain $lower$ and $upper$） The number of intervals and within .

Interval and $S(i,j)$ It means that $nums$ in , Location slave $i$ To $j$ The sum of the elements of , contain $i$ and $j$ ($i\le j$).

Tips ：

• $1<=nums.length<=10^5$
• $-2^{31}<=nums[i]<=2^{31}-1$
• $-10^5<=lower<=upper<=10^5$
• The question data guarantees that the answer is 32 position The integer of

Ideas ：
Use prefix and find $sum[i]$, So for $i$, Can traverse violently $j,(1\le j\le i-1)$ To calculate $sum[i]-sum[j]$ Get the satisfaction interval and $[lower,upper]$ The number of . At this time, the whole time complexity $O(n^2)$, It's bound to time out . At this point, I think I can use tree array to solve .
$lower\le sum[i]-sum[j]\le upper\Rightarrow sum[i]-upper\le sum[j]\le sum[i]-lower$.
That is, calculate at $[sum[i]-upper,sum[i]-lower]$ The number of . Using a tree array can quickly $O(logn)$ I'll get . however $sum[i]$ There's a wide range of data , Corresponding tree array $tr[n+1]$ Also great , And will cross the border . So we need to discretize . Discretization relies on ordered sets + Hash table . Discretization requires All the numbers used Are stored in an ordered set , Then map these numbers to $[1,max]$. The subsequent operations only need to go to the right $[1,max]$ Just operate on .

class Solution {
    

    int[] tr;
    int max;

    public int countRangeSum(int[] nums, int lower, int upper) {
    
        int n = nums.length;
        long[] sum = new long[n+1];
        for(int i = 1; i <= n;i++) {
    
            sum[i] = sum[i-1] + nums[i-1];
        }
        TreeSet<Long> set = new TreeSet<>();
        set.add(0l);
        for(long x : sum) {
    
            set.add(x);
            set.add(x - lower);
            set.add(x - upper - 1);
        }
        Map<Long,Integer> map = new HashMap<>();
        int idx = 1;
        for(long x : set) {
    
            map.put(x,idx++);
        }
        tr = new int[idx+1];
        max = idx;
        int res = 0;
        for(long x : sum) {
    
            res += sum(map.get(x - lower)) - sum(map.get(x - upper - 1));
            add(map.get(x),1);
        }
        return res;
    }

    public int lowbit(int x) {
    
        return x & (-x);
    }

    public void add(int x, int c) {
    
        for(int i = x; i <= max;i += lowbit(i)) {
    
            tr[i] += c;
        } 
    }

    public int sum(int x) {
    
        int res = 0;
        for(int i = x; i >= 1; i -= lowbit(i)) {
    
            res += tr[i];
        }
        return res;
    }
}