线段树 #

参考链接:https://juejin.cn/post/7024450888727003143

前言 #

首先提出一个问题：对于一个长度为n的序列，进行以下操作：

给下标为x的位置的数加上c，简称 modify 求区间 [ L, R ] 的和 ，简称 query

有下列几种方法可以实现

利用数组实现操作，modify的时间复杂度为O(1)，query的时间复杂度为O(N) 利用前缀和数组，modify的时间复杂度为O(N)，query的时间复杂度为O(1)

如果题中要求进行m次modify或者query操作，那么时间复杂度就会变成O(n*m)，很多情况下会超时；于是，树状数组站出来了； 树状数组对这两种操作的时间复杂度进行了折中处理

modify复杂度为O(log n) query 复杂度为O(log n)

原理 #

​ query
拿求区间 sum=[1,12] 的和举个例子；由图例可知 sum= c[12] + c[8] 又因为8=12-lowbit(12)，所以 sum= c[12] + c[12-lowbit(12)] 于是推出区间求和操作 sum=[1,R]= c[R] + c[R-lowbit(R)] + c [ temp - lowbit(temp)]+.... (temp=R-lowbit(R))

function query(x)//查询区间1~x的区间和；
{
	let res=0;
	for(let i=x;i>=1;i-=lowbit(i)) res+=tr[i];
	return res; 
}

modify
那么更改位置x的数值以后，怎样更新区间的数值呢？ eg：更新a[5]位置 的值，执行操作a[5]+=c;

首先a[5]这个位置要加上c，也就是 c[5]+=c 然后找子节点和父节点对应关系：c[5]对应的父节点为 c[6] ，c[6]对应的父节点为c[8], c[8]对应的父节点为c[16] 也就是 5 ——> 6 ——> 8 ——> 16 转化关系为 6 =5+lowbit(5) ； 8 =6+lowbit(6) ； 16=8+lowbit(8)

所以子节点更新父节点的方式就是，每次加上自身的lowbit

function modify(x,c)//修改树状数组x位置的值
{
	for(let i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

上述就是树状数组的基本原理，对于由父节点找子节点，由子节点找父节点的二进制原理，以及lowbit的基本原理，这里没有介绍；感兴趣的同学可以去b站找视频或者csdn等了解下； 模板

function lowbit(x)
{
	return x&-x;
}
function modify(x,c)//修改树状数组x位置的值
{
	for(let i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
function query(x)//查询区间1~x的区间和；
{
	int res=0;
	for(let i=x;i>=1;i-=lowbit(i)) res+=tr[i];
	return res; 
}

实际作用 #

简单说下树状数组能解决的问题：

单点修改，区间求和（利用模板即可） 区间修改，单点查询（做差分树状数组） 区间修改，区间求和（做差分树状数组，做前缀树状数组）

（能用树状数组解决的问题都能用线段树解决，树状数组原理难理解，但代码简单；线段树原理简单，代码长）

leetcode例题 #

2179.统计数组中好三元组数目（困难）
题目：
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。

好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。

请你返回好三元组的 总数目 。
示例 1：

输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3] 输出：1 解释： 总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。 这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。
示例 2：

输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3] 输出：4 解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。

提示：

n == nums1.length == nums2.length 3 <= n <= 105 0 <= nums1[i], nums2[i] <= n - 1 nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。

解：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var goodTriplets = function(nums1, nums2) {
    let n =nums1.length,res=0
    // 哈希表存储nums2每个元素出现的位置 为了好算线段树，位置从1开始
    let map = new Map()
    for(let i=0,n=nums2.length;i<n;i++){
        map.set(nums2[i],i+1)
    }
    // 线段树存储已遍历过的nums1中元素对应nums2中的位置
    let tree = Array(n+1).fill(0)
    // 线段树模版
    let lowbit = (x) => x & -x
    let modify = (idx, x) => {
        for(;idx<=n;idx+=lowbit(idx))tree[idx]+=x
    }
    let sum = (idx) => {
        let res = 0
        for(;idx>=1;idx-=lowbit(idx))res+=tree[idx]
        return res
    }
    // 遍历nums1
    for(let i =0;i<n;i++){
        // 将nums1当前元素放到对应nums2的位置
        let idx = map.get(nums1[i])
        // 统计左边出现过的元素个数
        let left = sum(idx)
        // 统计右边没出现过的元素个数 = 右边的位置数 - 右边出现的个数
        // 右边共有(n-idx)个位置,右边出现的个数 = 已经出现的-左边出现的 = i-left 
        let right = n - idx - i + left
        // 加上当前遍历元素能形成的好三元组数目
        res+=(left*right)
        // 将当前元素放入用以更新线段树
        modify(idx,1)
    }
    return res
};