刚刚学习LIS最长上升子序列的时候，网上找了一文，里面有个解法是用树状数组来优化的

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define rg register int
using namespace std;

int n;
int s[200005];

struct su{
    int v,id; //按照权值为第一关键字保证算法正确性
    inline bool operator <(su x){
        if(v==x.v)return id>x.id; //按照序号从大到小可以保证所求为上升子序列
        return v<x.v; //（针对标号）因为相同权值的数，前面的状态不能转移给后面
    }                 //（针对标号）从大到小枚举就不会出现这种情况
}a[200005];

inline void add(int x,int y){
    for(;x<=n;x+=x&-x) s[x]=max(s[x],y);
}

inline int ask(int x){
    rg res=0;
    for(;x>=1;x-=x&-x) res=max(s[x],res);
    return res;
}

int main(){
    cin>>n;
    for(rg i=1;i<=n;++i)
        cin>>a[i].v,a[i].id=i;
    sort(a+1,a+n+1);
    for(rg i=1;i<=n;++i)
        add(a[i].id,ask(a[i].id)+1);
    cout<<ask(n)<<endl;
    return 0;
}

请问里边的add函数和ask函数中for循环的那个x+=x&-x和x-=x&-x是什么意思？
能用非位运算表达式写吗？

有关算法的地方其实我是看不懂的，现在只学习了少部分的语法，所以以下说法只是个人意见
首先，如果是学习算法和说据结构的话还是用自己的理解去敲代码，不要看百度（根据个人经验，我面对算法方面的一旦复制粘贴我不理解的句子，整串代码一旦出现不是自己想要的结果，我将不知道该如何去改正，就算别人帮忙改正了，也是半迷糊）
其实，你这串代码，我是看不懂的，看不懂的地方有很多
1#define rg register int
像这种宏定义除了c出现的次数多，其实c++很多书是不允许这样的，会导致代码的可读性很差，而且效率不好，最好还是使用define进行标题保护比较好
再看看register 这个关键字，太老了吧，c++11已经不让使用了，c++17已经抛弃但是保留关键字
最后你提问的是关于x-=x&-x
这和bieset有关，bitset又和2进制有关，and这个符号的意思是两者都是1结果才是1，否则为0，
就比如y=1&3，结果是1
1如果是四位数的话那就是 std::bitset<4> bits { 0b0001 };
3  如果是四位数的话 std::bitset<4> bits { 0b0011 };
0001+0011=0001，换成10进制的话就是1，
最后关于位运算是比较绕脑的，我也不怎么熟悉，只能说个大概

谢谢啊，我都不知道11以上已经加了自动优化了。。。

-x是x取反加1
假设x的而二进制是
bbbb1010000
-x二进制就是
bbbb0110000
x最低的1右边本来是0 取反加1之后还是0
x最低的1左边的数据原来是1就变成0 原来是0 就变成1
&操作之后 最低的1左边的数据全部是0 右边全部是0&0
最后只剩下最低的1

后面的分析对着树状数组的示意图理解
x+=x&-x就是遍历树状数组里面 包含这个节点的父节点
比如你修改了节点6 那么节点6的父节点 节点8也需要调整 节点8的父节点以此类推

x-=x&-x比较难描述他访问的前缀节点 对着示意图理解一下

[此贴子已经被作者于2020-4-11 23:30编辑过]

谢谢大佬