wordpress英文版语言包,镇江优化推广,wordpress上传文件,网站开发教程免费lowbit操作
数字二进制表达中的最低位1以及后面所有的0#xff0c;函数写法如下#xff1a;
int lowbit(int x){return x-x;}
例如说#xff0c;lowbit(0101100100) (100)
lowbit(4) 4 lowbit(6) 2
时间复杂度o(1)
树状数组
应用
进行单点修改和区间查询…lowbit操作
数字二进制表达中的最低位1以及后面所有的0函数写法如下
int lowbit(int x){return x-x;}
例如说lowbit(0101100100) (100)
lowbit(4) 4 lowbit(6) 2
时间复杂度o(1)
树状数组
应用
进行单点修改和区间查询时间复杂度为O(logn) 结构 进行单点修改 修改t[i]然后 iilowbit(i) 修改t[i]
进行区间查询 查询区间和就拆分成求前缀和求(a,b)就拆成(1,b)-(1,a-1)
ii-lowbit(i)
修改和查询函数的代码 注意一定是 0
例题 愉悦值的计算就是求区间和
有两个操作修改和查询使用树状数组的数据结构。
#include iostream
using namespace std;const int N 1e7;
using ll long long;
ll a[N],t[N];
int n;int lowbit(int x) {return x-x;}void update(int k,ll x)
{a[k] x;for(int i k ; i n ;i lowbit(i)) t[i] x;
}ll getprefix(int k)
{ll res 0;for(int i k ; i 0 ; i - lowbit(i)) res t[i];return res;
}ll getsum(int l,int r)
{return getprefix(r) - getprefix(l-1);
}ll oper(int k,int n)
{return (2*k-n-1)*a[k]-getsum(1,k-1)getsum(k1,n);
}int main()
{// 请在此输入您的代码int m;cin n m;for(int i 1 ; i n ; i) {ll x;cin x;update(i,x);}while(m--){int op;cin op;if(op 1){int x;ll z;cin x;cin z;update(x,z-a[x]);}else {int x;cin x;cout oper(x,n) \n;}}return 0;
}
