Đăng nhập để hỏi chi tiết
< cần giải thích >
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
TRẢ LỜI
Có 1 cách khác ngoài dùng BIT, DPT tương đương nhưng BIT nhanh hơn, đó là Segment tree
DPT: nlog(n) + qlog(n)
Code C++:
#include<bits/stdc++.h>
#define ll long long
#define forr(i,l,r) for(ll i=l;i<=r;i++)
#define fodd(i,l,r) for(ll i=l;i>=r;i--)
#define all(v) v.begin(),v.end()
#define llmax LLONG_MAX
#define imax INT_MAX
#define pb push_back
using namespace std;
const int mod=1e9+7;
int a[100011],n,t;
ll tree[400011];
void update(int id,int l,int r,int &u,int &d)
{
if(l>r||u<l||r<u) return;
if(l==r)
{
tree[id]+=d-a[u];
return;
}
tree[id]+=d-a[u];
int m=(l+r)/2;
update(id*2,l,m,u,d);
update(id*2+1,m+1,r,u,d);
}
ll getans(int id,int l,int r,int &u,int &v)
{
if(l>r||r<u||v<l) return 0;
if(u<=l&&r<=v) return tree[id];
int m=(l+r)/2;
return getans(id*2,l,m,u,v)+getans(id*2+1,m+1,r,u,v);
}
int main(){
cin.tie(0);ios_base::sync_with_stdio(0);
cin>>n>>t;
while(t--)
{
int xd,x,y; cin>>xd>>x>>y;
if(xd==1)
{
update(1,1,n,x,y);
a[x]=y;
}
else cout<<getans(1,1,n,x,y)<<'\n';
}
}
Hãy giúp mọi người biết câu trả lời này thế nào?
54 vote
Dùng BIT.
ĐPT: O(qlogn)
$\\$
Code tham khảo:
#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll a[N], bit[N];
int n, q;
ll getsum(int p) {
int idx = p; ll res=0;
while (idx > 0) {
res += bit[idx];
idx -= (idx & (-idx));
}
return res;
}
void update(int u, int v) {
int idx = u;
while (idx <= n) {
bit[idx] += v;
idx += (idx & (-idx));
}
}
int main() {
cin >> n >> q;
while (q--) {
int type, x, y; cin >> type >> x >> y;
if (type == 1) {
update(x, y - a[x]);
a[x] = y;
}
else cout << getsum(y) - getsum(x-1) << endl;
}
}
$\\$
(Đã AC trên VNOJ)
$\\$
$\\$
$\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}$
Hãy giúp mọi người biết câu trả lời này thế nào?
54 vote
Bạn muốn hỏi điều gì?
Đặt câu hỏiPH/HS Tham Gia Nhóm Lớp 10 Để Trao Đổi Tài Liệu, Học Tập Miễn Phí!
Educational Segment Tree Contest - ITEZ2
Bạn được cho một mảng gồm n số nguyên. Ban đầu tất cả các số của mảng đều là 0. Nhiệm vụ của bạn là xử lí 2 loại truy vấn:
• Loại 1 có dạng 1 x y: Gán phần tử ở vị trí thứ 2 trong dãy thành số y (1 ≤ x ≤n, g| <10)
• Loại 2 có dạng 2 1 r: In ra t ...
Bảng tin
Bạn muốn hỏi điều gì?
Đặt câu hỏi
Cơ quan chủ quản: Công ty Cổ phần Công nghệ Giáo dục Thành Phát
Tải ứng dụng
Inbox: m.me/hoidap247online
Trụ sở: Tầng 7, Tòa Intracom, số 82 Dịch Vọng Hậu, Cầu Giấy, Hà Nội.
Giấy phép thiết lập mạng xã hội trên mạng số 331/GP-BTTTT do Bộ Thông tin và Truyền thông.
76
5711
54
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int M = 1e6 + 5; long long n, q, k, a[M], b[M], t[4*N], ti[4*N]; void up(int id, int l,int r, int i, int val){ if (l>i || r<i) return ; if(l == r){ t[id] = val; // a[i] = val; return; } int mid = (l+r)/2; up(id*2, l, mid, i, val); up(id*2+1, mid + 1, r,i, val); t[id] = t[id*2] + t[id*2+1]; } void build(int id, int l, int r){ if(l==r){ t[id] = a[l]; return; } int mid = (l+r)/2; build(id*2, l, mid); build(id*2+1,mid+1,r); t[id] = t[id*2] + t[id*2+1]; } long long tichmax(long long id, long long l, long long r, long long u, long long v){ if ( v<l || u>r) return 0; if (u <= l && r<= v) return t[id]; long long mid = (l + r)/2; long long q1 = tichmax(id*2, l, mid, u, v); long long q2 = tichmax(id*2 + 1, mid+1, r, u ,v); return q1+q2; } int main(){ cin>>n>>q; // for(int i = 1;i<=n;i++) cin>>a[i]; // build(1,1,n); while(q--){ int l, r; cin>>k>>l>>r; if(k==1) up(1,1,n,l,r); if(k==2){ cout<<tichmax(1,1,n,l,r)<<"\n"; } } } Rút gọn#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int M = 1e6 + 5; long long n, q, k, a[M], b[M], t[4*N], ti[4*N]; void up(int id, int l,int r, int i, int val){ if (l>i || r<i) return ; if(l == r){ t[id] = val; // a[i] = v... xem thêm