第六章： 二分查找与二叉排序树

二分查找基础知识

已知一个排序数组A，和另外一个乱序数组B，求B中某一个任意元素是否再A中出现，出现用1代表，未出现用0代表，结果储存到C里面

例子

A = [-1,2,5,20,90,100,207,800]
B = [50,90,3,-1,207,80]
输出：C=[0,1,0,1,1,0]

最简单的方法是暴力搜索，对A和B里面的所有节点进行遍历 然而，这种情况下，如果A和B的元素相等为n，时间复杂度为O($n^2$) 有没有其他方法

方法1 二分查找法

只需要比较2次 二分查找的时间复杂度为O($\log{n}$)

用递归的方式实现二分查找
bool binary_search(std::vector<int> &sort_array,//排序数组，搜索到返回true，否则返回false
                   int begin, int end, int target){//待搜索区间的左端和右端
    if (begin > end){//如果右端再左端前面，区间不存在
        return false;
    }
    int mid = (begin + end) / 2;//中点
    if (target == sort_array[mid]){//判断是否是target
        return true;
    }
    else if (target < sort_array[mid]){//当小于的时候进左区间进行搜索
        return binary_search(sort_array, begin, mid-1, target);
    }
    else if (target > sort_array[mid]){//大于的时候进右区间进行搜索
        return binary_search(sort_array, mid + 1, end, target);
    }
}
用循环的方式来实现二分查找
bool binary_search(std::vector<int> &sort_array,//排序数组
                   int target){//搜索区间
    int begin = 0;//初始化begin和end为起始点和终点
    int end = sort_array.size() - 1;
    while(begin <= end){//当区间存在的时候进行查找
        int mid = (begin + end) / 2;
        if (target == sort_array[mid]){
            return true;
        }
        else if (target < sort_array[mid]){
            end = mid - 1;
        }
        else if (target > sort_array[mid]){
            begin = mid + 1;
        }
    }
    return false;
}

一般来讲，分治思想的算法很容易用循环来替代递归，但是回溯思想的算法很难用循环来实现

插入位置

#easy 35. 搜索插入位置 - 力扣（LeetCode） 给定一个排序数组nums(无重复元素)和目标值target,如果target在nums里面出现，则返回target所在下标，如果target再nums里面未出现，则返回target应该插入位置的数组下标，使得将target插入数组nums后，数组仍然有序

样例

输入: nums = [1,3,5,6], target = 5
输出: 2

解决方法如下

class Solution {

public:

    int searchInsert(std::vector<int>& nums, int target) {

        int index = -1;//最终返回的下标，初始化为-1

        int begin = 0;//返回区间左端点

        int end = nums.size() - 1;//返回区间右端点

        while (index == -1){//如果index == -1说明还未找到正确位置，持续二分搜索，不管找没找到都会更新index的数值

            int mid = (begin + end) / 2;

            if (target == nums[mid]){//如果找到target

                index = mid;

            }

            else if (target < nums[mid]){

                if (mid == 0 || target > nums[mid - 1]){

                    index = mid;

                }

                end = mid - 1;//如果target小于中点，更新区间右端点

            }

            else if (target > nums[mid]){

                if (mid == nums.size() - 1 || target < nums[mid + 1]){

                    index = mid + 1;

                }

                begin = mid + 1;//如果target大于中点，更新区间右端点

            }

        }

        return index;

    }

};

区间查找

#medium 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） 给定一个排序数组nums(nums中右重复元素)与目标值target，如果target出现，则返回左右端点下标，如果targets在nums里面没出现，返回[-1,-1] 示例

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

对左端点进行查找 对右端点进行查找 在不满足的条件的情况下进行下一次的二分查找直到查到该点为止 解决方法如下

int left_bound(std::vector<int>& nums, int target){//查找左侧端点

    int begin = 0;//初始化begin和end

    int end = nums.size() - 1;

    while(begin <= end){//区间存在进行循环

        int mid = (begin + end) / 2;

        if (target == nums[mid]){//当查找到target

            if (mid == 0 || nums[mid -1] < target){//正好在边界或者该点的前面一点比target小

                return mid;//说明该点就是左端点

            }

            else end = mid - 1;//如果不是，把end设置为mid - 1(即更新区间为该点的左侧区间)继续查找

        }

        else if (target < nums[mid]){//二分查找传统艺能

            end = mid - 1;

        }

        else if (target > nums[mid]){

            begin = mid + 1;

        }

    }

    return -1;

}

  

int right_bound(std::vector<int>& nums, int target){//同left_bound

    int begin = 0;

    int end = nums.size() - 1;

    while(begin <= end){

        int mid = (begin + end) / 2;

        if (target == nums[mid]){

            if (mid == nums.size() - 1 || nums[mid + 1] > target){//当mid为右端点或者mid的右侧比target大

                return mid;

            }

            else begin = mid + 1; //更新右区间

        }

        else if (target < nums[mid]){

            end = mid - 1;

        }

        else if (target > nums[mid]){

            begin = mid + 1;

        }

    }

    return -1;

}

  

class Solution {

public:

    std::vector<int> searchRange(std::vector<int>& nums, int target) {

        std::vector<int> result;

        result.push_back(left_bound(nums, target));//所有函数启动启动启动，还有这个

        result.push_back(right_bound(nums, target));

        return result;

    }

};

旋转数组查找

#medium 33. 搜索旋转排序数组 - 力扣（LeetCode） 给定一个排序数组nums (无重复元素)，且nums可能以某个未知的下标进行旋转，给定目标值target，求target是否在nums里面出现，如果出现返回所在下标，未出现返回-1,算法时间复杂度要求O($\log{n}$) 旋转

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

示例

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

算法思路 递增区间可以直接使用二分查找，旋转区间是新的旋转数组，可以用图里面的算法进行查找 解决方法如下

class Solution {

public:

    int search(std::vector<int>& nums, int target) {

        int begin = 0;//定义begin 和 end

        int end = nums.size() - 1;

        while(begin <= end){

            int mid = (begin + end);//定义mid

            if (target == nums[mid]){//如果target 为mid 直接返回

                return mid;

            }

            else if (target < nums[mid]){//如果target小于mid

                if (nums[begin] < nums[mid]){//如果数组的开始小于中点，说明该数组是递增数组，begin一定大于end

                    if (target >= nums[begin]){//如果target比begin大，说明该点在[begin mid-1]里面

                        end = mid - 1;

                    }

                    else{//反之，说明该点在[mid+1 end]里面

                        begin = mid + 1;

                    }

                }

                else if (nums[begin] > nums[mid]){//如果begin比mid大，说明旋转区间在前面，[begin mid-1]为旋转数组，[mid+1 end]为递增数组

                    end = mid -1;//直接在[begin mid - 1]里面查找，由于target < mid 而且后面为递增数列

                }

                else if (nums[begin] == nums[mid]){//如果相等，说明只有两个元素 说明在[mid+1 end]里面，target要是mid就直接返回了

                    begin = mid + 1;

                }

            }

            else if (target > nums[mid]){//大于的情况

                if (nums[begin] < nums[mid]){//前面为递增，后面为旋转，target>mid，目标必然在旋转区间里面

                    begin = mid + 1;

                }

                else if (nums[begin] > nums[mid]){//前面为旋转，后面为递增，两个区间都有可能

                    if (target >= nums[begin]){//如果target > begin 在旋转区间，begin > end 而且 后面为递增区间

                        end = mid - 1;

                    }

                    else{//反之，在前面进行查找

                        begin = mid + 1;

                    }

                }

                else if (nums[begin] == nums[mid]){//说明只有两个元素，查找后半部分

                    begin = mid + 1;

                }

            }

        }

        return -1;

    }

};

二叉查找（排序）树

是一颗可以查找的二叉树

若左子树不空，则左子树上所有节点值均小于或等于它的根节点的值； 若右子树不空，则右子树上所有节点的值军大于或等于它的根节点值 左右子树也分别为二叉排序树 等于的情况只能出现在左子树或右子树的某一侧

由于二叉查找树的中序遍历是从小到大的，故又名二叉排序树

        8
       / \
      3   10
     / \    \
    1   6    15

二叉查找树的数据结构和二叉树的结构完全相同，但是二叉查找树可以查找，废话

二叉查找树插入节点

代码实现

struct TreeNode {//树
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void BST_insert(TreeNode *node, TreeNode *insert_node){//当前节点和待插入节点
    if (insert_node->val < node->val){//如果插入节点小于当前节点，插入左树
        if (node->left){//有左树的情况
            BST_insert(node->left, insert_node);//递归
        }
        else{
            node->left = insert_node;//直到没有左数后作为左树
        }
    }
    else{//如果插入节点大于等于当前节点，插入右数
        if (node->right){//有右树
            BST_insert(node->right, insert_node);//递归
        }
        else{//右子树为空时，将node的右指针与待插入节点相连接
            node->right = insert_node;
        }
    }
}

P.S.尽量不要把算法和内存维护放在一起

二叉树查找数值

代码实现

struct TreeNode {//树
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool BST_search(TreeNode *node, int value){
    if (node->val == value){//查找到的时候返回true
        return true;
    }
    if (value < node->val){//当查找值小于该节点。进左树
        if (node->left){//如果该点有左树，递归
            return BST_search(node->left, value);
        }
        else{//否则没找到
            return false;
        }
    }
    else{//反之
        if (node->right){//如果该点有右树，递归
            return BST_search(node->right, value);
        }
        else{//否则没找到
            return false;
        }
    }
}

二叉树的编码与解码

#medium 449. 序列化和反序列化二叉搜索树 - 力扣（LeetCode） 给定一个二叉查找树，对该函数进行编码和解码 编码

将二叉树转化为字符串

解码

把字符串转为二叉查找树

预备知识 ： 二叉查找树前序遍历与复原

注意：只有前序遍历得到的结果才能复原

编码

解决方法如下

    string serialize(TreeNode* root) {//编码函数
        std::string data;//新建编码字符串
        BST_preorder(root, data);
        return data;
    }
解码

解决方法如下

 TreeNode *deserialize(std::string data) {
        if (data.length() == 0){//判空
        	return NULL;
        }
        std::vector<TreeNode *> node_vec;//提取data中的数字作为二叉查找树的节点
        int val = 0;//初始化val
        for (int i = 0; i < data.length(); i++){//把data作为数值push进树的val中
        	if (data[i] == '#'){
        		node_vec.push_back(new TreeNode(val));//把valpush进树并新建节点
        		val = 0;//重置val
        	}
        	else{
        		val = val * 10 + data[i] - '0';//把字符串转为整型
        	}
        }
        for (int i = 1; i < node_vec.size(); i++){
            BST_insert(node_vec[0], node_vec[i]);//把这些节点插入树里面
        }
        return node_vec[0];//返回树的根节点
    }
};
/*新建的树的节点是不能delete的*/
其他函数
void BST_insert(TreeNode *node, TreeNode *insert_node){//二叉树插入节点
    if (insert_node->val < node->val){
        if (node->left){
            BST_insert(node->left, insert_node);
        }
        else{
            node->left = insert_node;
        }
    }
    else{
        if (node->right){
            BST_insert(node->right, insert_node);
        }
        else{
            node->right = insert_node;
        }
    }
}

void change_int_to_string(int val, std::string &str_val){//整型转换为字符串
    std::string tmp;
    while(val){//遍历val，把val里面的最低位转化为字符，添加到temp的尾部
        tmp += val % 10 + '0';//取出val里面的最低位
        val = val / 10;//更新val直到val到0为止
    }
    for (int i = tmp.length() - 1; i >= 0; i--){//逆序将字符串添加到str_val中
        str_val += tmp[i];//添加
    }
    str_val += '#';//将#作为分割符
}

void BST_preorder(TreeNode *node, std::string &data){//前序遍历二叉排序树，将node->val转换为字符串至str_val
    if (!node){
        return;
    }
    std::string str_val;
    change_int_to_string(node->val, str_val);
    data += str_val;//将新得到的字符串与老字符串相连
    BST_preorder(node->left, data);
    BST_preorder(node->right, data);
}

逆序数

#hard 315. 计算右侧小于当前元素的个数 - 力扣（LeetCode） [[第四章：递归，回溯和分治#逆序数|本题是该题的第二种解法]]当然第二种解法没完成，你可以看看第三种解法 已知数组nums，求新数组count，count[i] 代表nums[i]右侧且比nums[i]小的数字 示例

nums = [5,2,6,1],counts = [2,1,1,0]
nums = [6,6,6,1,1,1] counts = [3,3,3,0,0,0]
二叉搜索树的实现

#未完成 需要找出一个O($n\log{n}$)的算法 而n个元素插入二叉树平均时间复杂度正好是O($n\log{n}$)

设计一个记录左子树数量的二叉查找树

算法思路

解决方法如下

struct BSTNode {//记录左子树的二叉查找树

    int val;

    int count;//左子树计数器

    BSTNode *left;

    BSTNode *right;

    BSTNode(int x) : val(x), left(NULL), right(NULL), count(0) {}

};

  

void BST_insert(BSTNode *node, BSTNode *insert_node, int &count_small){//当前节点和插入节点

    if (insert_node->val <= node->val){//当插入节点小于等于当前节点，注意这里是小于等于

        node->count++;//当前节点的count计数++

        if (node->left){//有左树继续走

            BST_insert(node->left, insert_node, count_small);

        }

        else{//没左树为左树

            node->left = insert_node;

        }

    }

    else{//如果插入节点比当前节点大

        count_small += node->count + 1;//待插入节点的count为当前节点的count＋1

        if (node->right){

            BST_insert(node->right, insert_node, count_small);

        }

        else{

            node->right = insert_node;

        }

    }

}

/*实现代码*/

class Solution {

public:

    std::vector<int> countSmaller(std::vector<int>& nums) {

        std::vector<int> result;//最终逆序数组

        std::vector<BSTNode *> node_vec;//二叉查找树节点池

        std::vector<int> count;//从后向前插入过程中的count_small数组

        for (int i = nums.size() - 1; i >= 0; i--){

            node_vec.push_back(new BSTNode(nums[i]));//从后向前创建节点并push进节点池

        }

        count.push_back(0);//第一个节点count_small为0

        for (int i = 1; i < node_vec.size(); i++){//将第二个节点到第n个节点插入到第一个节点为根的二叉排数中，在插入过程中计算每一个节点的count_small

            int count_small = 0;

            BST_insert(node_vec[0], node_vec[i], count_small);

            count.push_back(count_small);

        }

        for (int i = node_vec.size() - 1; i >= 0; i--){

            delete node_vec[i];//释放节点空间

            result.push_back(count[i]);//逆序的方法push会result

        }

        return result;//返回result

    }

};

然而。。。。。这个代码在leetcode仍然无法完全通过，他的时间复杂度为O($n\log{n}$)因为二叉树不是平衡的，可能会导致节点链过长甚至退化成一条链，此时再插入新节点需要遍历整棵树，最坏的情况下为O($n^2$)

真不愧是你啊byd乐扣

想要补救可以改成自平衡二叉查找树，比如红黑树，但是我还不会：( 4-揭秘2-3-4树与红黑树的等价关系_哔哩哔哩_bilibili 手把手带你实现红黑树（c++） - 知乎 (zhihu.com) 自己学去吧

二叉索引树（fenwick树）的实现

#完成 本题还可以用线段树来实现，与BIT差不多，应用更广，但是更麻烦

树状数组的基本知识

二叉索引树又被称为树状数组，用于解决动态前缀和问题的数据结构 树状数组从1开始 主要功能

询问区间[L,R]的求和（区间查询） 修改序列a某个元素的值（单点修改）

区间\[L,R]的长度为R的“二进制分解”下最小的二次幂

可以利用$\text{lowbit}(x) = x \operatorname{and} (-x)$ 来实现计算x的二进制分解下的二次幂

对于给定的数组为a，设树状数组为c，则c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和 根据lowbit函数可以建立如下森林 想要找到[1,x],可以从x-lowbit(x)开始往前找 c[x]维护的是在[x-lowbit(x)+1,x]之间所有数字的和 区间查询 

    int query(int i, vector<int>& tree) {

        int presum = 0; // 初始化前缀和为0

        while (i > 0) { //循环，直到i<0为止，i一开始的值为x

            presum += tree[i]; //计算总和

            i -= lowbit(i); //往前移动lowbit(i) 刚好是原数组的对应区间的前一个，去处理该点对应的tree

        }

        return presum; // 返回前缀和

    }
    /*tree数组里面tree[i]的值为原数组[x-lowbit(x)+1,x]里面所有值的和*/

单点修改 

    void add(int i, int delta, vector<int>& tree) {

        while (i < tree.size()) { //tree[tree.size()]为整颗树的父节点，从tree[i]开始向上修改，直到超过父节点为止

            tree[i] += delta; // 更新树状数组中的值

            i += lowbit(i); // 计算下一个需要更新的位置

        }

    }

初始化一个树状数组

可以等效于对每一个节点都单点修改，时间复杂度O($n\log{n}$) 或者考虑每个节点对父节点的贡献，时间复杂度O($n$)

方法二的代码如下

void init(){
    for(int i = 1;i<=n;i++){
        tree[i]+=a[i];//将该点赋值给tree
        if(i+lowbit(i)<= n){//当当前遍历的点还没到整棵树的总父节点时候
        tree[i+lowbit(i)]+=tree[i]//将自己本身加给自己的父节点
        }
    }
}

除此之外树状数组还支持区间修改，单点查询；区间修改，区间查询

离散化

把无限空间的有限个体映射到有限空间，提升算法效率 在只关注相对大小时，可以进行离散化 比如

C=1,5,8,10,999,999,10^32
经过离散化
c = 1,2,3,4,4,5

相当于把数值转化为他的下标

离散化本质上是一种哈希，大整数，浮点数，字符串都可以进行离散化

简单的代码实现

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int a[200000+10];
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    //进行排序，左闭右开
    std::sort(a+1,a+n+1);
    //去重，返回一个迭代器，指向数组去重后不重复序列中最后一个元素的下一个下标
    int len = unique(a+1,a+n+1)-(a+1); //参数是去重的起始点和截止点,返回的迭代器于数列头部的差值恰好为去重后数组长度 uique只是把重复的元素放在数组末尾不进行访问，而不是删除
    //建立下标
    for(int i = 1;i<=len;i++){
        cout <<a[i]<<' ';
    //返回一个迭代器，指向第一个大于等于该元素的元素，与数组头元素的指针之间的距离恰好为其对应的下标 
        a[i] = lower_bound(a+1,a+n+1,a[i]) - a;
        cout<<a[i]<<'\n' ;
    } 
}
利用离散化二叉搜索树来实现本题

思路如下，我们对nums进行离散化，备份进a里面。在执行过程中，从后往前遍历nums，利用getID找到当前num[i]对应的下标，由于BIT的下标从1开始，所以离散值域的下标也要加1，每插入一个nums[i],就对树状数组的源数组的目标位置（离散值域的nums[i]对应的下标位置加一）加一，同时维护其父节点， 比如

nums = [5,2,6,1,1]
    a = [1,2,5,6]
    当遍历到1的时候
    c[1] = 1 c[2]=1  c[3] = 0 c[4]= 1
    当遍历到第二个1
    c[1] = 2 c[2]=2  c[3] = 0 c[4]= 2
    当遍历到6的时候
    c[1] = 2 c[2]=2  c[3] = 0 c[4]= 3
    .....

此时，nums该点对应树的节点的前一个节点的前缀和就是该点的逆序数 比如

    当遍历到1的时候
    c[1] = 1 c[2]=1  c[3] = 0 c[4]= 1
    逆序数为0
    当遍历到第二个1
    c[1] = 2 c[2]=2  c[3] = 0 c[4]= 2
    逆序数为0
    当遍历到6的时候
    c[1] = 2 c[2]=2  c[3] = 0 c[4]= 3
    逆序数为c[3]+c[2] = 2
    ......

代码实现如下

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
private:
    vector<int> c; // 树状数组
    vector<int> a; // 离散化后的值域

    void Init(int length) { // 初始化树状数组
        c.resize(length, 0);
    }

    int LowBit(int x) { // 计算 x 的最低位
        return x & (-x);
    }

    void Update(int pos) { // 在树状数组中更新一个位置的值
        while (pos < c.size()) {
            c[pos] += 1;
            pos += LowBit(pos);
        }
    }

    int Query(int pos) { // 查询树状数组中一个位置之前的前缀和
        int ret = 0;

        while (pos > 0) {
            ret += c[pos];
            pos -= LowBit(pos);
        }

        return ret;
    }

    void Discretization(vector<int>& nums) { // 对输入序列进行离散化
        a.assign(nums.begin(), nums.end());//将nums里面数值赋值到a
        sort(a.begin(), a.end());//对a进行排序
        a.erase(unique(a.begin(), a.end()), a.end());//对a去重后去掉重复元素
    }
    
    int getId(int x) { // 获取一个元素在离散化后值域中的下标
        return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
    }
public:
    vector<int> countSmaller(vector<int>& nums) { // 计算右侧小于当前元素的个数
        vector<int> resultList;

        Discretization(nums); // 离散化

        Init(nums.size() + 5); // 初始化树状数组
        
        for (int i = (int)nums.size() - 1; i >= 0; --i) { // 从后往前遍历输入序列
            int id = getId(nums[i]); // 获取当前元素在离散化后值域中的下标
            resultList.push_back(Query(id - 1)); // 查询树状数组中 id-1 位置之前的前缀和，即右侧小于当前元素的个数
            Update(id); // 在树状数组中更新 id 位置的值
        }

        reverse(resultList.begin(), resultList.end()); // 翻转结果列表

        return resultList;
    }
};

另一个代码思路 主要思路相同，只不过换了一种离散化的方式 这个思路采用stl::unordered_map 来进行离散化 注意：unordered_map内部采用哈希表，没有顺序，不能根据下标进行遍历 unordered_map的下标运算符接收一个键作为参数，并返回与该键相关联的值 ，如果没有的话会新建这个映射关系 由于unordered_map的特性，它可以自动建立映射关系，在遍历uniques数组时候，重复的元素会被覆盖掉，只保留最后一个的秩次映射关系，达到去重的操作 比如

    std::unordered_map<int,int> rank_map
    rank_map = {{3,5},{4,6}};
    printf("%d",rank_map[3]);
    printf("%d",rank_map[4]);

这个代码的输出为5，6

class Solution {

public:

    vector<int> countSmaller(vector<int>& nums) {

        int n = nums.size(); // 输入数组的大小

        vector<int> res(n); // 结果数组，初始值为0

        vector<int> tree(n + 1); // 树状数组，初始值为0

        unordered_map<int, int> rank_map; // 用于存储离散化后的秩次信息

        // 离散化

        vector<int> uniques(nums); // 创建一个新的数组，用于存储输入数组中的唯一元素

        sort(uniques.begin(), uniques.end()); // 对唯一元素进行排序

        for (int i = 0; i < uniques.size(); i++) {

            rank_map[uniques[i]] = i + 1; // 将唯一元素映射到它们的秩次

        }

        // 从右往左查询

        for (int i = n - 1; i >= 0; i--) { // 从右往左遍历输入数组

            int rank = rank_map[nums[i]]; // 获取当前元素的秩次

            res[i] += query(rank - 1, tree); // 查询秩次比当前元素小的元素数量，并将其存储在结果数组中

            add(rank, 1, tree); // 在树状数组中更新当前元素的秩次信息

        }

        return res; // 返回结果数组

    }

private:

    // lowbit函数：二进制最低位1所表示的数字

    int lowbit(int x) {

        return x & (-x);

    }

    // 单点更新：执行+delta

    void add(int i, int delta, vector<int>& tree) {

        while (i < tree.size()) { // 遍历树状数组中需要更新的位置

            tree[i] += delta; // 更新树状数组中的值

            i += lowbit(i); // 计算下一个需要更新的位置

        }

    }

    // 前缀和查询

    int query(int i, vector<int>& tree) {

        int presum = 0; // 初始化前缀和为0

        while (i > 0) { // 遍历树状数组中需要查询的位置

            presum += tree[i]; // 累加前缀和

            i -= lowbit(i); // 计算下一个需要查询的位置

        }

        return presum; // 返回前缀和

    }

};
下课!