트 리 배열 모드 (구간 업데이트, 구간 조회, 단일 업데이트, 단일 조회)
1507 단어 데이터 구조
#include
using namespace std;
#define ll long long
#define mem(a, b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define DBG printf("this is a input
")
//D[i]
ll sum1[500005]; //D[1]+D[2]+D[3]+...+D[i]
ll sum2[500005]; //D[1]+2*D[2]+3*D[3]+...+n*D[n];
int n , m, num[500005];
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int x , int k)//
{
int xi = x;
while(x <= n)
{
// k
sum1[x] += k;
sum2[x] += k*(xi-1);
x += lowbit(x);
}
}
ll get_sum (int x) //1-x
{
ll sum= 0;
int xi = x;
while(x > 0)
{
sum += xi * sum1[x] - sum2[x];
x -= lowbit(x);
}
return sum;
}
int main(void)
{
mem(num,0);
mem(sum1,0);
mem(sum2,0);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> num[i];
update(i, num[i] - num[i - 1]); //
}
while(m --)
{
int z;
cin>>z;
if(z == 1)
{
int l , r , k;
cin>>l>>r>>k;
//
update(l,k);
update(r+1,0-k);
}
else
{
int k;
cin>>k;
//
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.