抽象化字符串，经典之作树型计算机程序之一，标识符十分钟，但其蕴含着的演算法价值观却十分绝妙。能这么说，刷演算法题却要学抽象化字符串，那当然称得上两大惋惜。
抽象化字符串，常见于高效率处置「两个字符串的预览以及后缀和的求得」。
取值两个宽度为 n 的字符串 nums，需要全力支持三类操作方式：操作方式 1: 将 nums[i] 的值增加 v操作方式 2: 求得 nums[1] + nums[2] + ... + nums[i] 的值对前述问题，假如咱换用直接的作法，则操作方式 1 的前夕维数为 O(1)，操作方式 2 的前夕维数为 O(n)。倘若总共有 q 次操作方式，则总的前夕维数为 O(qn)。
而假如使用抽象化字符串来解，则操作方式 1 和操作方式 2 的前夕维数均为 O(log(n))。倘若总共有 q 次操作方式，则总的前夕维数为 O(qlog(n))。对照以后的作法，抽象化字符串的数学预测在前夕维数上有实质性的竞争优势，而这也便是咱自学该演算法的其原因。
抽象化字符串抽象化字符串大力推进演算的关键，在于对十进制的更进一步发掘，因而我们第两个步来自述呵呵十进制。
以自然数 29 为例，其十进制为 11101，因而 29 能依照其十进制更进一步则表示为：
依照而此特征，咱能再次思索以后的「操作方式 2」，即如何INS13ZD求得字符串 [1, 29] 的和？
仿效以后对 29 的十进制分拆，咱也完全能将 [1, 29] 分拆成如下表所示五个区段的相乘：
检视前述五个区段，能发现五个区段的宽度依序为 2^4、2^3、2^2、2^0。因此对每两个区段来深入探讨，其区段宽度正好等同于「区段右西北侧十进制中最高位的 1 相关联的值」。以区段 [2^4 + 1,2^4 +2^3] 为例，其区段宽度为 2^3，而其区段右西北侧为 2^4 +2^3，十进制为 11000，其中最高位的 1 在第 3 位，相关联的值为 2^3，正好等同于其区段宽度。
lowbit(x)为了更快地公理化叙述前述检视，咱导入 lowbit(x) 表达式，则表示「x 十进制中最高位的 1 相关联的值」。比如 29，其十进制为 11101，则最高位的 1 在第 0 位，相关联的值为 2^0，即 lowbit(29)=1。再比如说 16，其十进制为 10000，则最高位的 1 在第 4 位，相关联的值为 2^4，即 lowbit(16)=16。
int lowbit(x) { return x & (-x);}标识符十分短，但想要理解却需要一些原码、补码的知识。简单来深入探讨，在计算机中，所有整数都是用补码的形式来存放的，对自然数 x 来深入探讨，其补码形式就是其十进制的形式。但对负数 -x 来深入探讨，咱需要将 x 的十进制形式按位取反再加 1。
依旧以 29 和 16 为例，因此用 8 位十进制的形式来则表示：
原理教学有了 lowbit(x) 表达式，咱能更容易地则表示 [1, 29] 的分拆形式：
由此一来，咱能更容易地发现五个区段的宽度依序为 lowbit(16)、lowbit(24)、lowbit(28)、lowbit(29)，即 2^4、2^3、2^2、2^0。
到了而此步，咱便推导出了抽象化字符串 c 的含义，即 c[x] 则表示区段 [x - lowbit(x) + 1,x] 的和，即：
因而 [1, 29] 的和能则表示为：
由此，咱能得到抽象化字符串关于操作方式 2，即求得 [1, x] 区段和的标识符：
int query(int x) { int res=0; // 当 i 等同于 0 时，退出 for 循环 for (int i=x; i; i -=lowbit(i)) res +=c[i]; return res;}至此，还剩下两个表达式未教学。即对操作方式 1 来深入探讨，当 nums[i] 的值增加了 v，抽象化字符串 c 该如何变化？
由于 c[x] 则表示区段 [x - lowbit(x) + 1, x] 的和，因而咱只要将所有覆盖了 nums[i] 的 c[x] 均加上 v 即可。由此问题转变为了「如何寻找到所有覆盖了 nums[i] 的 c[x]」？
寻找的方法十分简单，咱先直接给出标识符：
void update(int x, int v) { // n 为抽象化字符串的宽度 for (int i=x; i <=n; i +=lowbit(i)) c[i] +=v;}检视前述标识符，咱能发现只要令 i 不断加上 lowbit(i)，即可预览所有相关联区段覆盖了 nums[i] 的 c[x]。
想要理解这个结论，咱需要先思索 i + lowbit(i) 到底意味着什么？
咱假设 nums[i]=109，查看 nums[i] 能否通过不断加 lowbit(i) 预览到 c[128]，即相关联 [1, 128] 的区段。
109 的十进制为 01101101，其不断加 lowbit(i) 的结果如下表所示：
检视前述结果，最终的确预览到了 128。事实上，109 相关联的十进制中，「最高位的 1 前面的 0」的位置分别是 1、4、7。在其不断加 lowbit(i) 的过程中，最高位的 1 不断向前挪到最近的两个 0，即 110、112、128 最高位的 1 分别为 1、4、7。
因而咱能发现，不断加 lowbit(i) 的过程，即为将十进制中最高位的 1 不断向前挪到最近的两个 0 的过程。
回到前面的问题，「为什么令 i 不断加上 lowbit(i)，即可预览所有相关联区段覆盖了 nums[i] 的 c[x]」？
咱假设 c[x] 相关联的区段 [x - lowbit(x) + 1, x] 覆盖了 nums[i]，且 c[x] 最高位 1 的位置为 pos。则 nums[i] 的十进制形式在 [0, pos] 位中必定存在 1。
此时分两种情况，若 nums[i] 十进制的 pos 位为 1，则 nums[i]=x；若 nums[i] 十进制的 pos 位不为 1，则 nums[i] 在不断加 lowbit(i) 的过程中，最高位的 1 一定会挪到 pos 位，即在加 lowbit(i) 的过程中达到 x，由此能证明以后的结论。
树型结构教学完抽象化字符串的原理后，咱再给出抽象化字符串的树型图，来帮助各位更进一步理解该计算机程序。
上图最下边一行为 nums 字符串，代表 n 个叶节点，其上方为抽象化字符串 c，满足以下 5 条性质：
每个内部节点 c[x] 保存以它为根的子树中所有叶节点的和每个内部节点 c[x] 的值等同于其子节点值的和每个内部节点 c[x] 的子节点个数为 lowbit(x) 的位数除树根外，每个内部节点 c[x] 的父节点为 c[x + lowbit(x)]树的深度为 O(log(n))，其中 n 则表示 nums 字符串的宽度总结呵呵，抽象化字符串全力支持在 O(log(n)) 的前夕维数内「求字符串区段和」或「预览字符串中某一点的值」，其完整标识符如下表所示所示：
int n; // 抽象化字符串宽度vectorc;int lowbit(x) { return x & (-x);}void update(int x, int v) { for (int i=x; i <=n; i +=lowbit(i)) c[i] +=v;}int query(int x) { int res=0; for (int i=x; i; i -=lowbit(i)) res +=c[i]; return res;}
习题自学307. 位置和检索 - 字符串可改写题目叙述给你两个字符串 nums ，请你完成三类盘查，其中一类盘查要求预览字符串下标相关联的值，另一类盘查要求返回字符串中某个范围内元素的总和。
实现 NumArray 类：
NumArray(int[] nums) 用整数字符串 nums 初始化对象void update(int index, int val) 将 nums[index] 的值预览为 valint sumRange(int left, int right) 返回子字符串 nums[left, right] 的总和（即，nums[left] + nums[left + 1], ..., nums[right]）示例
输入：["NumArray", "sumRange", "update", "sumRange"][[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]输出：[null, 9, null, 8]解释：NumArray numArray=new NumArray([1, 3, 5]);numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5])=9numArray.update(1, 2); // nums=[1,2,5]numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5])=8
提醒
1 <=nums.length <=30000-100 <=nums[i] <=1000 <=index < nums.length-100 <=val <=1000 <=left <=right < nums.length最多调用 30000 次 update 和 sumRange 方法
该题属于抽象化字符串的模板题，咱来依序查看其要实现的表达式。
首先是用 nums 字符串初始化抽象化字符串 c，这时通常有两种操作方式，第一种是调用 n 次 update 表达式，前夕维数为 O(nlog(n))，标识符如下表所示：
for (int i=1; i <=n; i++) update(i, nums[i]);第二种是依照以后的树型结构，每两个内部节点 c[x] 的值等同于其所有子节点值的和，因而能实现 O(n) 前夕维数内的初始化，标识符如下表所示：
for (int i=1; i <=n; i++) { c[i] +=nums[i]; int j=i + lowbit(i); if (j <=n) c[j] +=c[i];}下一步是第二个表达式，将 nums[i] 的值预览为 val。而以后抽象化字符串中的 update 操作方式为将 nums[i] 的值增加 val。因而咱需要「保存」或「求出」nums[i] 的目前值，再令其增加 val - nums[i] 即可。
最后是第三个表达式，求 nums 字符串在 [i, j] 上的区段和。以后抽象化字符串的 query 操作方式能求 [1, x] 的区段和，因而 [i, j] 的区段和等同于 query(j) - query(i - 1)。
标识符实现
class NumArray {public: int n; vectorc; int lowbit(int x) { return x & (-x); } void update_c(int x, int v) { for (int i=x; i <=n; i +=lowbit(i)) c[i] +=v; } int query(int x) { int res=0; for (int i=x; i; i -=lowbit(i)) res +=c[i]; return res; } NumArray(vector& nums) { n=nums.size(); c.clear(); c.resize(n + 1, 0); for (int i=1; i <=n; i++) { c[i] +=nums[i-1]; int j=i + lowbit(i); if (j <=n) c[j] +=c[i]; } } void update(int index, int val) { val -=query(index + 1) - query(index); update_c(index + 1, val); } int sumRange(int left, int right) { return query(right + 1) - query(left); }};
315. 计算右侧小于目前元素的个数
题目叙述
取值两个整数字符串 nums，按要求返回两个新字符串 counts。字符串 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例
输入：nums=[5,2,6,1]输出：[2,1,1,0] 解释：5 的右侧有 2 个更小的元素 (2 和 1)2 的右侧仅有 1 个更小的元素 (1)6 的右侧有 1 个更小的元素 (1)1 的右侧有 0 个更小的元素提醒
0 <=nums.length <=100000-10000 <=nums[i] <=10000
解题思路该题与抽象化字符串经典之作题「逆序对个数」差不多一样，假设 (i, j) 为逆序对，则满足：
i < jnums[i] > nums[j]回到本题，题目要求 nums[i] 右侧小于它的元素个数。因而咱从右往左遍历 nums 字符串，因此定义两个新字符串 a，若遍历到 nums[i]，则令 a[nums[i]]=1。
因而 counts[i] 即为字符串 a 中 [-10000, nums[i] - 1] 的区段和。由于字符串的下标为非负数，因而咱将 nums[i] 中所有数都加上 10001，将其原来的范围 [-10000, 10000] 移动到 [1, 20001]。
再用抽象化字符串维护字符串 a，即可完成此题，具体细节见下述标识符。
标识符实现
class Solution {public: int n; vectorc; int lowbit(int x) { return x & (-x); } void update(int x, int v) { for (int i=x; i <=n; i +=lowbit(i)) c[i] +=v; } int query(int x) { int res=0; for (int i=x; i; i -=lowbit(i)) res +=c[i]; return res; } vectorcountSmaller(vector& nums) { for (int i=0; i < nums.size(); i++) nums[i] +=10001; n=2e4 + 1; c.resize(n + 1, 0); for (int i=nums.size() - 1; i >=0; i--) { int v=nums[i]; nums[i]=query(v - 1); update(v, 1); } return nums; }};
493. 翻转对
取值两个字符串 nums ，假如 i < j 且 nums[i] > 2 * nums[j] 咱就将 (i, j) 称作两个重要翻转对。
你需要返回取值字符串中的重要翻转对的数量。
示例 1
输入: [1,3,2,3,1]输出: 2示例 2
输入: [2,4,3,5,1]输出: 3注意
取值字符串的宽度不会超过50000。输入字符串中的所有数字都在32位整数的则表示范围内。
该题与上题思路基本一致，上题要求的是：
i < jnums[i] > nums[j]但本题要求的是：
i < jnums[i] > 2*nums[j]因而咱依然能从右往左遍历 nums 字符串，因此定义两个新字符串 a，若遍历到 nums[i]，则令 a[2 * nums[i]]=1，即 update(2 * nums[i], 1)。
对 i，求所有满足要求的 j，即为 query(nums[i] - 1)。
但本题还有两个关键点，即 nums[i] 的值可能很大，咱开不下这么大的空间。
每当接触这种情况时，咱就需要换用「离散化」的手段。「离散化」的原理是将所有可能出现的数，如 2 * nums[i] 或 nums[i] 都存入字符串，先排序再去除重复，然后再依序编号。
比如 nums[i] 原字符串为 [1, 1, 1000000, 2]，则所有可能出现的数为 [1, 2, 1, 2, 1000000, 2000000, 2, 4]。将其排序，得到 [1, 1, 2, 2, 2, 4, 1000000, 2000000]。再去重得到 [1, 2, 4, 1000000, 2000000]。
因而咱能将所有的 1 映射为 1，2 映射为 2，4 映射为 3，1000000 映射为 4，2000000 映射为 5。
由此抽象化字符串的大小则不再取决于 nums[i] 的大小，而取决于 nums 字符串的宽度。
使用「离散化」的技术，咱即可完成此题，具体细节见下述标识符。
class Solution {public: int n; vectorc; int lowbit(int x) { return x & (-x); } void update(int x, int v) { for (int i=x; i <=n; i +=lowbit(i)) c[i] +=v; } int query(int x) { int res=0; for (int i=x; i; i -=lowbit(i)) res +=c[i]; return res; } int reversePairs(vector& nums) { // 离散化 setst; unordered_mapmp; for (int i=0; i < nums.size(); i++) { st.insert(nums[i]); st.insert(2ll * nums[i]); } int idx=0; for (auto x:st) mp[x]=++idx; n=idx; c.resize(n + 1, 0); // 解 int ans=0; for (int i=nums.size() - 1; i >=0; i--) { ans +=query(mp[nums[i]] - 1); update(mp[2ll * nums[i]], 1); } return ans; }};
本文主要教学了「抽象化字符串」演算法，该演算法的核心功能为，能在 O(log(n)) 的前夕维数内「求字符串区段和」或者「预览字符串中某一点的值」。
简单来深入探讨，假如接触同时全力支持「求区段和」以及「单点操作方式」的计算机程序题，则能往「抽象化字符串」的方向思索。
除此之外，该演算法通过十进制的分拆，用 O(log(n)) 的效率代替了 O(n) 的简单作法，其演算法价值观也值得咱花前夕好好理解。
