index |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
value |
5 | 6 | 2 | 8 | 10 | 1 | 4 |
2~5 = 26
1~7 = 36
共 \(N\) 個元素,進行 \(Q\) 次 \((N,Q \le 5 \times 10^5)\)
新增一個數列,第 \(k\) 個存 1~k
的總和
index |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
value(V) |
5 | 6 | 2 | 8 | 10 | 1 | 4 |
prefix sum(P) |
5 | 11 | 13 | 21 | 31 | 32 | 36 |
區間 [l,r]
總合為 \(P_r-P_{l-1}\) ,特別定義 \(P_0=0\)
code
const int N=500010;
int n;
int v[N],psum[N];
// 建構 prefix sum 陣列
for(int i=1;i<=n;++i){
psum[i]=psum[i-1]+v[i];
}
差分是跟前綴和相反的操作,每一項都存與前一項的差
index |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
value(V) |
5 | 6 | 2 | 8 | 10 | 1 | 4 |
Difference(D) |
5 | 1 | -4 | 6 | 2 | -9 | 3 |
技巧 | 單點修改 | 區間修改 | 區間查詢 |
---|---|---|---|
前綴和 | \(O(n)\) | \(O(n)\) | \(O(1)\) |
差分 | \(O(1)\) | \(O(1)\) | \(O(n)\) |
BIT | \(O(\log_2{(n)})\) | \(O(n\log_2{(n)})\) | \(O(\log_2{(n)})\) |
歸納出
first code
int POW(int a,int x){
if(x==0) return 1;
if(x==1) return a;
if(x%2==1) return POW(a,x/2)*POW(a,x/2)*a;
// x%2==0
return POW(a,x/2)*POW(a,x/2);
}
分析複雜度 \((\) 或讓電腦跑跑看 \()\)
if(x%2==1) return POW(a,x/2)*POW(a,x/2)*a;
// x%2==0
return POW(a,x/2)*POW(a,x/2);
nice code
int POW(int a,int x){
if(x==0) return 1;
if(x==1) return a;
int t=POW(a,x/2);
if(x%2==1) return t*t*a;
// x%2==0
return t*t;
}
複雜度 \(O(\log_2(x))\)
其實沒有那麼複雜
簡化版
int POW(int a,int x){
if(x==0) return 1;
if(x%2==1) return POW(a,x-1)*a;
// x%2==0
int t=POW(a,x/2);
return t*t;
}
想像將 \(a^x\) 中的 \(x\) 以二進位表示
while 迴圈實作
using ll=long long;
const ll MOD=1e9+7;
ll POW(ll a,ll x){
ll ret=1;
while(x>0){
if(x%2==1) ret=ret*a%MOD;
a=a*a%MOD;
x/=2;
}
return ret;
}
vector<int> v(1000);
// 這樣也可以用來輸入
for(int &i:v){
cin>>i;
}
for(int a:v){
cout<<a<<" ";
}
舉個有趣的例子(除了對…而言)
struct Friend{
string type,name;// ...
// 建構式
Friend(string _name,string tp="cf"){
name=_name;
type=tp;
}
friend operator<(Friend a,Friend b){
if(a.type=="gf"){
if(b.type=="gf"){
cout<<"你完蛋喽!"<<"\n";
}
return false;
}else if(a.type=="bf"){
if(b.type=="bf"){
cout<<"妳完蛋喽!"<<"\n";
}
return false;
}else{
return a.name<b.name;
}
}
}
struct Friends{
vector<Friend> fs;
void add_friend(string name,string type="cf"){
fs.emplace_back(name,type);
}
bool find_by_name(string name){
return count(fs.begin(),fs.end(),name);
}
bool find_gf(){
for(auto f:fs){
if(f.type=="gf"){
return true;
}
}
return false;
}
bool find_bf(){
for(auto f:fs){
if(f.type=="bf"){
return true;
}
}
return false;
}
void check(){
int a=0;
for(auto f:fs){
if(f.type=="gf" || f.type=="bf"){
a++;
}
}
if(a>1){
cout<<"你準備要去世喽!";
}
}
void sortFriends(){
sort(fs.begin(),fs.end());
}
void printFriends(){
for(auto f:fs){
cout<<setw(20)<<f.name<<f.type<<"\n";
}
}
}
int main(){
Friends mtmatt;
mtmatt.add_friend("dws(戴偉璿)");
mtmatt.add_friend("lju(李卓岳)");
mtmatt.add_friend("lj(羅傑)","ac");// acquaintance 點頭之交
mtmatt.add_friend("cpp","tool");
mtmatt.sortFriends();
mtmatt.printFriends();
}
or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing